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

这道题考试选择打表，完美爆零。。

算数基本定理：

任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=P₁^a₁ P₂^a₂…Pn^an，这里P₁<P₂<…<Pn均为质数，其诸指数ai是正整数。

这样的分解称为N的标准分解式。

约数和定理：

对于任意一个大于1的正整数N可以分解正整数：N=P₁^a₁ P₂^a₂…Pn^an，则由约数个数定理可知N的正约数有(a₁+1)(a₂+1)(a₃+1)…(an+1)个，那么N的(a₁+1)(a₂+1)(a₃+1)…(an+1)个正约数的和为f(N)=(P₁^0+P₁^1+P₁^2+…P₁^a₁)(P₂^0+P₂^1+P₂^2+…P₂^a₂)…(Pn^0+Pn^1+Pn^2+…Pn^an)。

至此，搜索算法很显然地露出水面——穷举Pi及其对应的ai进行搜索。

具体解释：

题目给的n可以分解为多个式子的乘积，式子中是互不相同质数的幂依次增加的和（如上图黄色部分）。每个式子最高次幂那一项的数的乘积即为所得答案之一（如上图绿色部分）。它的所有正约数之和为题目给的
n。

在深搜时要注意：有两种情况：①最后分解完，剩余得1，将所得结果记录②分解剩余的数-1是一个质数p，这样就可以看成p^0+p^1，也可以得到结果，将其记录（代码中有标注）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define N 100100
using namespace std;
ll prime[N],ans[N],sum,n;
bool notprime[N];
int cnt;
void getprime()//预处理出所有素数
{
     pos(i,2,N)
     {
        if(!notprime[i])
          prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<N;j++)
        {
           notprime[prime[j]*i]=1;
           if(i%prime[j]==0)
             break;
        }
     }
}
bool judge(ll x)//判断是否为素数
{
     if(x==1)
       return 0;
     for(ll i=1;prime[i]*prime[i]<=x;i++)
       if(x%prime[i]==0)
         return 0;
     return 1;
}
void dfs(ll now,int pos,ll left)//深搜 ，now表示目前所得的结果，pos表示搜索素数的位置，left表示目前剩余的数
{
     if(left==1)//①处解释
     {
       ans[++cnt]=now;
       return;
     }
     if(left-1>=prime[pos]&&judge(left-1))//②处解释
       ans[++cnt]=(left-1)*now;
     for(int i=pos;prime[i]*prime[i]<=left;i++)
     {
        for(ll tmp=prime[i]+1,tt=prime[i];tmp<=left;tt*=prime[i],tmp+=tt)
           if(left%tmp==0)
             dfs(now*tt,i+1,left/tmp);
     }
}
int main()
{
    getprime();
    while(scanf("%lld",&n)==1)
    {
       memset(ans,0,sizeof(ans));
       cnt=0;
       dfs(1,1,n);
       sort(ans+1,ans+cnt+1);
       printf("%d\n",cnt);
       pos(i,1,cnt-1)
         printf("%lld ",ans[i]);
       if(cnt)
         printf("%d\n",ans[cnt]);
    }
    while(1);
    return 0;
}

巴特西

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

最新文章

热门文章