时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。
可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 SS，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。
所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。
【输入】
输入包含 k 组数据。
对于每组数据，输入包含一个号码牌S。
【输出】
对于每组数据，输出有两行，第一行包含一个整数 m，表示有 m 个等的人。
第二行包含相应的 m 个数，表示所有等的人的号码牌。
注意：你输出的号码牌必须按照升序排列。
【输入样例】
42
【输出样例】
320 26 41
【提示】
数据范围与提示
对于 100% 的数据，k≤100, S≤2×109 。
sol：这道题初看时毫无思路，于是去看题解了，看到是搜索后一脸懵逼。。。
对于一个数
如果他是p1a1*p1a2*p3a3*~~*pnan
那么他的因数和就是 （p10+p11+p12+...+p1a1）*（p20+p21+...+p2a2）*...*（pn1+pn2+...+pnan）
于是可以爆搜p1~pn及其系数a1~an，随便弄点小剪枝居然就能过了，而且还飞快
剪枝（1），令当前的因数和为S，若（S-1）为质数，那么（S-1）*之前的几个系数显然是一种答案
剪枝（2），令当前的因数和为S，枚举质因数p，若p2>=S，这个p就是非法的，因为就算系数a是1， S除以（p+1）后S也小于p，而之后出现的质因数必须严格大于上一个（没有这个剪枝会T的很惨）
Ps：代码实现复杂度并不高
#includeusing namespace std;typedef int ll;inline ll read(){ ll s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){ if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')const int N=100005;int Prim[N],P_Cnt;bool Bo[N];inline void Pre_Prime(){ Prim[P_Cnt=0]=0; int i,j; int B=100000; for(i=2;i<=B;i++) { if(!Bo[i]) { Prim[++P_Cnt]=i; } for(j=1;j<=P_Cnt&&Prim[j]*i<=B;j++) {// printf("Shai %d*%d=%d\n",Prim[j],i,Prim[j]*i); Bo[Prim[j]*i]=1; if(i%Prim[j]==0) break; } }// printf("Cnt=%d\n",P_Cnt);// for(i=1;i<=P_Cnt;i++) Wl(Prim[i]);// exit(0); return;}int Num,Ans[N];inline bool Check_Prime(int x){ if(x<=100000) return (Bo[x])?(false):(true); int i; for(i=2;i*i<=x;i++) if(x%i==0) { return false; } return true;}//(p1^0+p1^1+...+p1^a1)*(p2^0+p2^1+...+p2^a2)*...*(pn^0+pn^1+...+pn^an)inline void dfs(int Last,int Shuz,int Sum){ if(Sum==1) { Ans[++*Ans]=Shuz; return; } if(Sum-1>Prim[Last]&&Check_Prime(Sum-1)) { Ans[++*Ans]=Shuz*(Sum-1); } int i,j,t; for(i=Last+1;i<=P_Cnt&&Prim[i]*Prim[i]<=Sum;i++) { t=Prim[i]; for(j=t+1;j<=Sum;t*=Prim[i],j+=t) if(Sum%j==0) { dfs(i,Shuz*t,Sum/j); } } return;}int main(){ Pre_Prime(); while(~scanf("%d",&Num)) { int i; *Ans=0; dfs(0,1,Num); sort(Ans+1,Ans+*Ans+1); *Ans=unique(Ans+1,Ans+*Ans+1)-Ans-1; Wl(*Ans); for(i=1;i<*Ans;i++) { W(Ans[i]); } if(*Ans) Wl(Ans[*Ans]); } return 0;}/*input428359output320 26 410*/