C++聪明的燕姿（数论、算术基本定理、素数筛）

C++聪明的燕姿（数论、算术基本定理、素数筛）

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。
可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！
燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S
，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。
所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）。
可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。
输入格式
输入包含 k组数据。
对于每组数据，输入包含一个号码牌 S。
输出格式
对于每组数据，输出有两行。第一行包含一个整数 m，表示有 m个等的人。第二行包含相应的 m个数，表示所有等的人的号码牌。
注意：你输出的号码牌必须按照升序排列。
数据范围
1≤k≤100,1≤S≤2×109
输入样例：
42
输出样例：
3
20 26 41

本题需要用到知识：
N = P1^a1 * P2^a2 * … * Pn^an
则N的约数个数为(a1+1)(a2+1)…(an+1)
约数之和S = (1+p1+p1^2 +…+p1^a1)
(1+p2+p2^2 +…+p2^ a2)…(1+pn+pn^2+ …+pn^an)
思路：
在sqrt(S)范围之内的素数枚举幂和，以S除之，能整除则继续枚举下一质数，直到S被除为1。

AC代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;const int N=50010;//保证包括sqrt(2*10^9)int primes[N],cnt=0;
bool st[N];
int ans[N],num;
int s;void get_primes(int n)
{for(int i=2;i<=n;++i){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]*i<=n;++j){st[primes[j]*i]=true;if(i%primes[j]==0) break;}}
}bool is_prime(int x)
{if(x<N) return !st[x];for(int i=0;primes[i]<=x/primes[i]&&i<cnt;++i)if(x%primes[i]==0) return false;return true;
}
//上一个质数的下标，拼凑出来的结果，S剩下的成分
void dfs(int last,int cur,int s)
{//把S拼凑出来了，当前拼凑的结果是答案if(s==1){ans[num++]=cur;return;}//保证s-1至少是2if(s-1>(last<0?1:primes[last])&&is_prime(s-1))ans[num++]=cur*(s-1);//用除法实现sqrt(s)复杂度，防爆intfor(int i=last+1;primes[i]<=s/primes[i];++i){for(int j=1+primes[i],t=primes[i];j<=s;t*=primes[i],j+=t)if(s%j==0) dfs(i,cur*t,s/j);}
}int main()
{memset(st,0,sizeof(st));get_primes(N-1);while(cin>>s){num=0;dfs(-1,1,s);cout<<num<<endl;if(num) {sort(ans,ans+num);for(int i=0;i<num;++i)cout<<ans[i]<<" ";cout<<endl;}}return 0;
}