POJ 3421 X-factor Chains | 数论

题意:

给一个x,求最长的排列满足开头是1,结尾是x,前一个数是后一个数的因子

输出长度和这样序列的个数

---

题解:

把x分解质因数,质因数个数就是答案,接下来考虑怎么求个数

显然这是一个可重集合全排列问题,设有n个元素

答案就是n!/每个元素出现次数的阶乘

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 typedef long long ll;

 #define N 2000

 using namespace std;

 int prime[N],n,cnt[N],pcnt,sum;

 ll jc[];

 bool isp[N];

 void init()

 {

     memset(isp,,sizeof(isp));

     isp[]=;

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

     {

     if (isp[i]==)

         prime[++pcnt]=i;

     for (int j=;j<=pcnt && i*prime[j]<N;j++)

     {

         isp[i*prime[j]]=;

         if (i%prime[j]==) break;

     }

     }

 }

 int main()

 {

     jc[]=;

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

     jc[i]=jc[i-]*i;

     init();

     while (scanf("%d",&n)!=EOF)

     {

     ll ans=;

     memset(cnt,,sizeof(cnt));

     sum=;

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

     {

         if (n==) break;

         while (n%prime[i]==)

         n/=prime[i],cnt[i]++,sum++;

     }

     if (n>)

         sum++;

     ans=jc[sum];

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

         ans/=jc[cnt[i]];

     printf("%d %lld\n",sum,ans);

     }

     return ;

 }