考试只筛到了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
",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
",tot);
sort(ans+1,ans+tot+1);
for(int i=1;i<tot;i++)
printf("%d ",ans[i]);
if(tot) printf("%d
",ans[tot]);
}
}