POJ 3421 素数+组合数学

　　　　　　　　　　　　　　　　　　　　X-factor Chains

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5741		Accepted: 1808

Description

Given a positive integer X, an X-factor chain of length m is a sequence of integers,

1 = X₀, X₁, X₂, …, X_m = X

satisfying

X_i < X_i₊₁ and X_i | X_i₊₁ where a | b means a perfectly divides into b.

Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

Input

The input consists of several test cases. Each contains a positive integer X (X ≤ 2²⁰).

Output

For each test case, output the maximum length and the number of such X-factors chains.

Sample Input

Sample Output

Source

POJ Monthly--2007.10.06, ailyanlu@zsu

分析：

x=a1^p1*a2^p2*...*an^pn

由于要求构造的序列最长，我们从序列最后一个开始，每次除以x的一个素因子

而一共可以除以∑pi次，所以可以构造的最长的长度就是∑pi

而有多少种方式呢？

其实就等价于p1个a1,p2个a2,...,pn个an,可以有多少种排列方式

明显，有(∑pi) ! / (p1!*p2!*...*pn!)个排列。

预处理：打出素数表

但是这道题还是tle了2次，原因：

1.打素数表不够高效(现在的打表方式很好)

2.有个地方还可以有很大的优化，写在注释了

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 
  5 using namespace std;
  6 
  7 const int maxn=1050000;
  8 
  9 bool is_prime[maxn];
 10 int prime[maxn>>1];
 11 int p[100];
 12 
 13 void init_prime()
 14 {
 15     memset(is_prime,true,sizeof is_prime);
 16     int i;
 17     is_prime[1]=false;
 18     for(i=4;i<maxn;i+=2)
 19         is_prime[i]=false;
 20     int e=(int)(sqrt(0.0+maxn)+1.0);
 21     int tot=1;
 22     prime[tot++]=2;
 23     for(i=3;i<e;i+=2)
 24     {
 25         if(is_prime[i])
 26         {
 27             prime[tot++]=i;
 28             int s;
 29             for(int j=i*i,s=2*i;j<maxn;j+=s)
 30                 is_prime[j]=false;
 31             //因为i为奇数，j也为奇数，j+奇数为偶数，不用考虑
 32             //由于j<n,i*i<n,则i<sqrt(n)
 33         }
 34     }
 35     for(;i<maxn;i+=2)
 36         if(is_prime[i])
 37             prime[tot++]=i;
 38 }
 39 
 40 int main()
 41 {
 42     init_prime();
 43     int x;
 44     while(~scanf("%d",&x))
 45     {
 46         if(x==1)
 47         {
 48             printf("0 0
");
 49             continue;
 50         }
 51         if(is_prime[x])
 52         {
 53             printf("1 1
");
 54             continue;
 55         }
 56         int cnt=1;
 57         int tot=0;
 58         while(x>1)
 59         {
 60             if(x%prime[cnt]==0)
 61             {
 62                 tot++;
 63                 p[tot]=0;
 64                 while(x%prime[cnt]==0)
 65                 {
 66                     x/=prime[cnt];
 67                     p[tot]++;
 68                 }
 69             }
 70             cnt++;
 71         }
 72         
 73         /*
 74         刚开始的做法
 75         memset(p,0,sizeof p);
 76         while(x>1)
 77         {
 78             while(x%prime[cnt]==0)
 79             {
 80                 x/=prime[cnt];
 81                 p[cnt]++;
 82             }
 83         cnt++;
 84         }
 85         这样的做法，数组p在范围1~cnt会有很多的无谓的0
 86         大大增加了后面循环的次数
 87         而且数组p也必须开得很大
 88         这样tle了
 89         优化之后，数组p在范围1~tot没有0
 90         tot相对于cnt小了很多
 91         数组p也只要100就够了
 92         一个优化，从tle到125ms
 93         */
 94         
 95         int sum=0;
 96         for(int i=1;i<=tot;i++)
 97             sum+=p[i];
 98         long long ans=1;
 99         for(int i=2;i<=sum;i++)
100             ans*=(long long)i;
101         for(int i=1;i<=tot;i++)
102         {
103             for(int j=2;j<=p[i];j++)
104                 ans/=(long long)j;
105         }
106         printf("%d %lld
",sum,ans);
107     }
108     return 0;
109 }

View Code