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

RainFestival · 2019-05-04 21:24:36 · 题解

我们知道，一个数的约数和是

它的每个质因子的各个次方之和再连乘

举个例子

360=2^3×3^2×5

约数和=(1+2^1+2^2+2^3)×(1+3^1+3^2)×(1+5^1)

所以我们枚举质数

先找出1-100000的质数

然后搜索质数前k次方和（质数不能重复）

就可以了

注意如果n-1也质数也要搜

我们可以确定，搜出的数不会重复，不会多，不会少

附上代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005],b[1000005],ans,sum,n,pri[100005],del,bo;
long long adddsum=0;
int is_prime(int ch)
{
    if (ch<2) return 0;
    for (int i=2;i*i<=ch;++i)
        if (ch%i==0) return 0;
    return 1;
}
void dfs(int k,int mmin,int sum)
{
    if (k==1)
    {
        ans++;
        b[ans]=sum;
        return;
    }
    else
    {
        if (k-1>=pri[mmin]&&is_prime(k-1)) dfs(1,-1,sum*(k-1));
        for (int i=mmin;pri[i]*pri[i]<=k;++i)
        {
            int p=1,add=1,now=pri[i];
            for (int j=1;p<=k;++j)
            {
                add=add*now;
                p=p+add;
                if (k%p==0) dfs(k/p,i+1,sum*add);
            }
        }
    }
}
int main()
{
    for (int i=2;i<=100000;++i) a[i]=1;
    for (int i=2;i<=100000;++i)
        if (a[i])
        {
            sum++;
            pri[sum]=i;
            for (int j=i;j<=100000/i;++j)
                a[i*j]=0;
        }
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=ans;++i)
            b[i]=0;
        ans=0;
        dfs(n,1,1);
        sort(b+1,b+ans+1);
        bo=0;    
        printf("%d\n",ans);
        if (ans==0) continue;
        for (int i=1;i<ans;++i)
            if ((i==1||b[i]!=b[i-1])&&b[i]!=0) bo=1,printf("%d ",b[i]);
        if ((ans==1||b[ans]!=b[ans-1])&&b[ans]!=0) bo=1,printf("%d",b[ans]);
        if (bo) putchar('\n');
    }
    return 0;
}

代码长度3.03k,时间76ms,内存3096KB

谢谢观赏