题解 P4397 【[JLOI2014]聪明的燕姿】

· · 题解

本蒟蒻的Blog

题解

对于一个数X对它分解质因数：

X=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}

则有：

\sum_{d|X}d=\prod_{i=1}^{k}{\sum_{j=0}^{c_k}{p_i^j}}

所以可先把所有小于\sqrt{S}质数筛出来。

然后暴力搜索每个因子的个数。

最后那个大于\sqrt{S}的质因子，暴力判一下即可。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
int S,p[4700],tot,ans[10000000];bool vis[45000];
inline void make_p()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=45000;i++)
    {
        if(!vis[i]) p[++p[0]]=i;
        for(int j=1;j<=p[0]&&p[j]*i<=45000;j++)
        {
            vis[i*p[j]]=true;
            if(i%p[j]==0) break;
        }
    }
}
inline bool IsPrime(int x)
{
    for(int i=2;i*i<=x;i+=(i&1)+1)
        if(x%i==0)
            return false;
    return true;
}
void DFS(int pn,int SN,int Num)
{
    if(SN==1)
    {
        ans[++tot]=Num;
        return;
    }
    if(SN>p[pn]&&IsPrime(SN-1)) ans[++tot]=Num*(SN-1);   //特判
    for(int i=pn;p[i]*p[i]<=SN;i++)        //枚举因子
    {
        LL t=p[i],sum=p[i]+1;
        for(;sum<=SN;t*=p[i],sum+=t)       //枚举因子个数
            if(SN%sum==0) 
                DFS(i+1,SN/sum,Num*t);
    }
}
int main()
{
    make_p();
    while(scanf("%d",&S)==1)
    {
        tot=0;DFS(1,S,1);
        printf("%d\n",tot);
        sort(ans+1,ans+1+tot);
        for(int i=1;i<=tot;i++)
            printf("%d%c",ans[i],i==tot?'\n':' ');
    }
    return 0;
}