AcWing 1296. 聪明的燕姿 题解 约数 DFS

题目

思路

题目意思是给定$k$个$s$，对于每个$s$，让我们求那些数的所有正约数的和等于$s$，求出来有多少个，并将它们升序输出。

• 因为求一个数的所有正约数的和为$s$，那么我们不难发现，这些个数必然是比$s$小的，因为他们的正约数里有$1$和他们本身。
• 另外，通过对算术基本定理的理解以及对一个数与它所有约数性质的观察，我们可以得出如下结论:（https://blog.csdn.net/weixin_45798993/article/details/122856747）
  
  
  
• 于是我们可以知道，$s$想等于一些数的所有正约数之和，那么$s$本身就得满足这样的性质：
  
  那么这样的话，可以知道满足所有正约数的和等于$s$的数可以表示为（$P_k$为质数）
  
  而我们可以试着算一算，虽然$s$的范围是$1\le S\le 2\times 10^9$
  但实际满足条件的$s$是很少的
  

因此我们可以采用暴搜的方式把它给搜出来。

• 再考虑一下剪枝
  

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5;  //因为1≤s≤10的9次方，我们用到的质数是小于sqrt(10的9次方的)
int cnt;
int primes[N];
bool st[N];
int s;
int ans[N],len=0;
void get_primes(int n)   //筛质数
{for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;if(i%primes[j]==0) break;}}
}
bool is_primes(int n)   //判断是否是质数
{if(n<N) return !st[n];   //如果小于N，可以直接在表格里查到for(int i=0;primes[i]<=n/primes[i];i++)  //如果大于N，看看它能不能被质数筛掉if(n%primes[i]==0) return false;  //筛掉了，是合数return true;  //筛不掉，是质数
}
void dfs(int last,int prod,int s)
{  //第一个参数，last:上一次用到的质数（我们这里是从小到大遍历质数的） prod：当前算出的这个数的部分解，s：剩余还需要被分解的if(s==1)  //如果s已经等于1了，说明被分解完了{ans[len++]=prod;  //这时的prod是最终的值，存进ansreturn;}if(s-1>(last<0?1:primes[last])&&is_primes(s-1)) ans[len++]=prod*(s-1);//特判特殊情况
//不return是因为Pi >= sqrt(s)只是我们枚举的一种情况而已，接下来还要枚举Pi < sqrt(s)的情况for(int i=last+1;primes[i]<=s/primes[i];i++){//枚举所有可能的质数int p=primes[i];//求j = 1 + Pi^1 + Pi^2 + ... + Pi^αifor(int t=p,j=p+1;j<=s;t*=p,j+=t)if(s%j==0) dfs(i,prod*t,s/j);  // 只有j是s的某一项，即j可以整除s，即s % j == 0才可以继续往下搜}
}
int main()
{get_primes(N-1);  //先筛一遍质数，把需要用到的数先处理出来while(scanf("%d",&s)!=EOF){len=0;dfs(-1,1,s);  //暴搜printf("%d\n",len);if(len>0){sort(ans,ans+len);for(int i=0;i<len;i++)printf("%d ",ans[i]);printf("\n");}}return 0;
}