X-factor Chains [POJ3421] [素数]

Description
    给定一个正整数X, 一个长度为m的X-因子链是由m+1个整数组成的。其中
    1 = X0, X1, X2, …, Xm = X 满足Xi < Xi+1 且 Xi 整除 Xi+1 。
    现在要求X-因子链的最大长度和最大长度有多少条？
Input
    多组数据，每一组数据一个正整数X (X ≤ 220).
Output
    对于每组数据，输出X-因子链的最大长度和最大长度有多少条
Sample Input
    2
    3
    4
    10
    100
Sample Output
    1 1
    1 1
    2 1
    2 2
    4 6
Analysis

1.子链的长度就是分解质因数后每个质因数个数的和。为什么？如果出现一个合数，必定可以再分解使子链加长。

2.剩下的工作就是dfs，注意每一步只能选泽一种质数去分解。分解到1记一个贡献

Code

 #include<set>

 #include<map>

 #include<queue>

 #include<stack>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;++i)

 #define per(i,a,b)    for(RG i=a;i>=b;--i)

 #define ll long long

 #define inf (1<<29)

 #define maxn 1048580

 #define lim 1048578

 using namespace std;

 int n,cnt,pt,ans,ans1;

 int isp[maxn],p[maxn];

 int num[maxn][];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void pre()

 {

     rep(i,,lim)

     {

         if(!isp[i])    p[++cnt]=i;

         for(RG j=;j<=cnt&&p[j]*i<=lim;j++)

         {

             isp[i*p[j]]=;

             if(!(i%p[j]))    break;

         }

     }

 }

 void work()

 {

     int res=n;

     rep(i,,cnt)

     {

         if(!(res%p[i])){

             num[++pt][]=p[i],num[pt][]=;

             while(!(res%p[i]))    ++num[pt][],res/=p[i],++ans1;

         }

         if(res==)    break;

     }

 }

 void dfs(int res)

 {

     if(res==){ans++;return;}

     for(int i=;i<=pt;i++)

     {

         if(num[i][])

         {

             num[i][]--;

             dfs(res/num[i][]);

             num[i][]++;

         }

     }

 }

 int main()

 {

     pre();

     while(~scanf("%d",&n))

     {

         pt=ans=ans1=;

         work();

         dfs(n);

         printf("%d %d\n",ans1,ans);

     }

     return ;

 }

巴特西

X-factor Chains [POJ3421] [素数]

最新文章

热门文章