PAT Basic 1096. 大美数

1. 题目描述：

若正整数 \(N\) 可以整除它的 4 个不同正因数之和，则称这样的正整数为“大美数”。本题就要求你判断任一给定的正整数是否是“大美数”。

2. 输入格式：

输入在第一行中给出正整数 \(K\)（\(≤10\)），随后一行给出 \(K\) 个待检测的、不超过 \(10^4\) 的正整数。

3. 输出格式：

对每个需要检测的数字，如果它是大美数就在一行中输出 Yes，否则输出 No。

4. 输入样例：

3
18 29 40

5. 输出样例：

Yes
No
Yes

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

一开始想着能找出大美数的规律，但是只能想到\(N\)为大美数时，4个不同正因数之和应为\(N,2N\)或\(3N\)。。。（因为4个不同正因数小于等于\(N\)，其和一定小于\(4N\)，不过这个条件好像没什么用），最后还是比较直接的思路：对于每个正整数\(N\)先找出其所有的正因数，再遍历这些正因数的所有组合情况依次判断，这里编写子函数judgeBigBeauty()进行逻辑判断，其中求解给定数组的所有组合情况的子函数combination()参考了：【递归+回溯】实现数组元素的组合、排列和全排列_数组元素组合方案_灰小猿的博客-CSDN博客 ，这里需要注意的一个细节是：因为C中数组作为参数时是以指针的形式传递，所以想获取数组大小的话需要额外再定义相关的参数。

AC后参考大佬的代码：1096 大美数 – PAT乙级真题_1096 大美数 柳诺_柳婼的博客-CSDN博客 ，一种比较简洁的思路，只能说智商被压制了。。。

My Code:

#include <stdio.h>

#define MAX_NUM 10000

int judgeBigBeauty(int num);
void combination(int *arr, int * ans, int k, int n, int arrLen, int ansLen, int *firstBlood, int num);

int main(void)
{
    int numCount = 0;
    int tempNum = 0;
    int i=0; // iterator
    
    scanf("%d", &numCount);
    for(i=0; i<numCount; ++i)
    {
        scanf("%d", &tempNum);
        if(judgeBigBeauty(tempNum))// judge num
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    
    return 0;
}

int judgeBigBeauty(int num)
{
    int factor[MAX_NUM] = {0};
    int factorCount=0;
    int i=0; // iterator
    int flag=0; // flag of BigBeauty
    int tempCombination[4];
    
    for(i=1; i*i<num; ++i) // find all factors of num
    {
        if(num % i == 0)
        {
            factor[factorCount++] = i;
            factor[factorCount++] = num/i;
        }
    }
    if(i*i == num) // add sqrt(num) if it's a factor of num
    {
        factor[factorCount++] = i;
    }
    
    if(factorCount<4) return 0; // the number of factor of num is less than 4, return false directly
    
    combination(factor, tempCombination, 0, 4, factorCount, 4, &flag, num);
    
    return flag;
}

// refer to https://blog.csdn.net/weixin_44985880/article/details/113434593
// find all combination of an array
/*
    arr: original array
    ans: the result combination of array
    k: the start element index of select
    n: number of selection
    arrLen: length of arr
    ansLen: length of ans
    firstBlood: flag of end recurse
    num: the num to be judged
*/
void combination(int *arr, int * ans, int k, int n, int arrLen, int ansLen, int *firstBlood, int num)
{
    // int arrLen = sizeof(arr)/sizeof(int);
    // int ansLen = sizeof(ans)/sizeof(int);
    // printf("arrLen: %d, ansLen: %d\n", arrLen, ansLen);
    if(n==0)
    {
        int tempSum = 0;

        for(int i=0; i<ansLen; ++i)
        {
            //printf("%d ", ans[i]);
            tempSum += ans[i];
        }
        //printf("\n");
        if(tempSum%num == 0)
        {
            *firstBlood = 1;
        }
        return;
    }
    for(int i=k; i<= arrLen-n && !(*firstBlood); ++i)
    {
        ans[ansLen-n] = arr[i];
        combination(arr, ans, i+1, n-1, arrLen, ansLen, firstBlood, num);
    }
}


// // refer to https://blog.csdn.net/liuchuo/article/details/126209590
// #include <stdio.h>

// int main(void)
// {
//     int numCount = 0;
//     int tempNum = 0;
//     int i=0; // iterator
//     int flag = 0;
    
//     scanf("%d", &numCount);
//     for(i=0; i<numCount; ++i)
//     {
//         scanf("%d", &tempNum);
//         flag = 0;
//         for(int a=1; a<=tempNum; ++a)
//         {
//             if(flag) break;
//             if(tempNum%a != 0) continue;
//             for(int b=a+1; b<=tempNum; ++b)
//             {
//                 if(flag) break;
//                 if(tempNum%b != 0) continue;
//                 for(int c=b+1; c<=tempNum; ++c)
//                 {
//                     if(flag) break;
//                     if(tempNum%c != 0) continue;
//                     for(int d=c+1; d<=tempNum; ++d)
//                     {
//                         if(flag) break;
//                         if(tempNum%d != 0) continue;
//                         if((a+b+c+d) % tempNum == 0) flag = 1;
//                     }
//                 }
//             }
//         }
        
//         printf("%s\n", flag?"Yes":"No");
//     }
    
//     return 0;
// }