【PAT乙级】1096 大美数 (15 分) DFS回溯解法

【PAT乙级】1096 大美数 (15 分) DFS回溯解法 题目

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

输入格式：
输入在第一行中给出正整数 K（≤10），随后一行给出 K 个待检测的、不超过 1e4 的正整数。

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

分析

先求出N所有因数
在所有因数里,4个一组枚举所有情况
可以四重for循环，也可以dfs

注意事项

a整除b是b÷a

代码(C++)

#include
using namespace std;
// 关于为什么要开200，因为一个数的因数个数上界不会超过2乘根号n
// 数字最大是1e4,开根后乘2就是200
const int N = 200;
int n,num;
int len;
int a[N];
bool used[N];
bool dfs(int step,int sum) {
    if(step==4) return sum%num==0;
    for(int i = 0;i>n;
    while(n--) {
        cin>>num;
        for(int i = 1;i<=num;i++) {
            if(num%i==0) a[len++] = i;
        }
        if(len<4) {
            cout<<"No"<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711237.html