考试只筛到了30分，正解dfs......
对于任意N=P1^a1*P2^a2*......*Pn^an,
F(N)=(P1^0+P1^1+...+P1^a1)(P2^0+P2^1+...+P2^a2)*...*(Pn^0+Pn^1+...+Pn^an)
从小到大枚举素数P，依次判定是否有K满足(P^0+P^1+...+P^K)|X
有一些细节需要处理，比如当前S为某大素数+1......
一开始打O(√n)一直T两个点，后来改成了O(√s)就过了。
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> using namespace std; int prime[100005],top,tot,ans[100005],n,ss; bool bo[100010]; void work() { for(int i=2;i<=100005;i++) { if(!bo[i]) prime[++top]=i; for(int j=1;j<=top&&i*prime[j]<=100005;j++){ bo[i*prime[j]]=1; if(!(i%prime[j])) break; } } } bool getp(int x) { for(int i=1;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) return 0; return 1; } void dfs(int s,int p,int now) { //printf("%d %d %d\n",s,p,now); if(s==1){ ans[++tot]=now; return ; } if((s-1)>prime[p]&&getp(s-1)) ans[++tot]=now*(s-1); for(int i=p+1;prime[i]*prime[i]<=s;i++) { long long t=1,all=1; for(int j=1;t<=s;j++) { all*=prime[i]; t+=all; if(s%t==0) dfs(s/t,i,now*all); } } } int main() { work(); while(scanf("%d",&n)!=EOF) { tot=0; ss=sqrt(n); dfs(n,0,1); printf("%d\n",tot); sort(ans+1,ans+tot+1); for(int i=1;i<tot;i++) printf("%d ",ans[i]); if(tot) printf("%d\n",ans[tot]); } }