BZOJ- 3629: [JLOI2014]聪明的燕姿

Description

设g(x)表示x的约数和。多组数据每次给你一个S，T<=100 ，S<=2*10^9，输出g(x)=S的所有x，从小到大输出。

将x质因子分解，，则
dfs，从小到大枚举质因子，枚举幂次，如果当前幂次不整除S，枚举下一个质因子，否则继续搜索。
记录S剩下的因数。
如果为1，那么当前即为一个解。
如果等于一个大于根号n的质数+1，那么当前解乘该质数即为一个解。
通过x< S可知，x中质因子大于根号S的只能有一个。
复杂度O(dfs)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
typedef long long ll;
int n,sq,pri[N],cnt,ans[N],tot;
bool v[N];
void initialize()
{
    int i,j;
    for(i=2;i<=100000;++i)
    {
        if(!v[i]) pri[++cnt]=i;
        for(j=1;i*pri[j]<=100000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
bool ispri(int x)
{
    if(x<=100000) return !v[x];
    for(int i=1;pri[i]*pri[i]<=x;++i)
        if(x%pri[i]==0) return 0;
    return 1;
}
void dfs(int now,ll tmp,int leave)
{
    if(leave==1){ans[++tot]=tmp; return ;}
    if(leave-1>sq &&ispri(leave-1)) ans[++tot]=tmp*(leave-1);
    int i; ll p,x;
    for(i=now;pri[i]<=sq;++i)
    {
        p=pri[i]; x=1;
        while(x+p<=leave)
        {
            x+=p; p*=pri[i];
            if(leave%x==0)
                dfs(i+1,tmp*p/pri[i],leave/x);
        }
    }
}
int main()
{
    initialize();
    while(~scanf("%d",&n))
    {
        sq=(int)sqrt(n)+1;
        tot=0;
        dfs(1,1,n);
        printf("%d\n",tot);
        sort(ans+1,ans+tot+1);
        for(int i=1;i<=tot;++i) printf("%d%c",ans[i],i==tot?'\n':' ');
    }
    return 0;
}