3629: [JLOI2014]聪明的燕姿|约数和|DFS

设$M(x)$为$x$的约数和，那么考虑约数和的求法，约数和显然是一个积性函数。
设

$$x=p_{1}^{t_{1}}*p_{2}^{t_{2}}*p_{3}^{t_{3}}*......*p_{n}^{t_{n}}$$
那么 $$M(x)=\sum_{c_{1}=0}^{t_{1}}p_{1}^{c_{1}}*\sum_{c_{2}=0}^{t_{2}}p_{2}^{c_{2}}*\sum_{c_{3}=0}^{t_{3}}p_{3}^{c_{3}}*......*\sum_{c_{n}=0}^{t_{n}}p_{n}^{c_{n}}$$
这样就可以考虑枚举质因子DFS转化为子问题继续求解。
$dfs(now,pos,rest)$是指搜索枚举到第$pos$个质因子，当前值为$now$,然后剩余的因子的和为$rest$时的解
搜索时枚举$\leq\sqrt n$的质因子，并且单独判断$rest-1$是否为质数，这样可以保证搜出来的解没有重复。

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<complex>
#include<queue>
#include<map>
#include<set>
#define N 45000
#define ll long long
using namespace std;
int top,a[N],prime[N],ans[N];
int n,tot;
void get_prime()
{
    for(int i=2;i<N;i++)
    {
        if(!a[i])
            prime[++top]=i;
        for(int j=1;prime[j]*i<N;j++)
        {
            a[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
bool jud(int x)
{
    if(x==1)return 0;
    for(int i=1;prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0)return 0;
    return 1;
}
void dfs(int now,int pos,int rest)
{
    if(rest==1)
    {
        ans[++tot]=now;
        return;
    }
    if(rest-1>=prime[pos]&&jud(rest-1))
        ans[++tot]=(rest-1)*now;
    for(int i=pos;prime[i]*prime[i]<=rest;i++)
        for(ll p=prime[i],sum=p+1;sum<=rest;p*=prime[i],sum+=p)
            if(rest%sum==0)
                dfs(now*p,i+1,rest/sum);
}
int main()
{
    get_prime();
    while(scanf("%d",&n)!=EOF)
    {
        tot=0;
        dfs(1,1,n);
        sort(ans+1,ans+tot+1);
        printf("%d\n",tot);
        for(int i=1;i<=tot;i++)
            printf("%d%c",ans[i],i==tot?‘\n‘:‘ ‘);
    }
    return 0;
}