这道题从Ac人数以及题目大意上看应属于简单题，但是我却做了好多天 ToT。
刚刚才看了一篇解题报告得到启发过的。题目有点tricky，给一个小于等于2^20的数，本质上要求质因子分解。
题目有接近1/3的提交是超时，其实分解质因子以及后面的计算没什么可说的，主要是求素数表这里会超时。
如果将2到2^20的所有素数打出来，程序长度超过可以提交的限制。如果打一部分，接着在程序里接着算也可以，不过
如果对质因子的上界估计不好的话，也要超时或导致效率低。
最小上界（上确界）是2^10，因为对于a<=2^20最多只有1个质因子会超过2^10，这用反证法很容易得到。因此我们只要算出1024以内
的172个素数即可，程序很快就跑完了。
另外打素数表的时候有一种比较快的算法，虽然只是在朴素算法基础上做了一些小的优化，不过即使在打1024以内素数表就可以体现出
优越性了（69ms VS 79ms），对于更大的素数表，优越性会更明显。
1 // pku 3421 给一个整数X,求X的分解。1=X0,X1,X2, ,Xm=X，其中Xi整除X(i+1)且Xi<X(i+1)，要求最大的m跟有多少种这样长度的链。
2 // 算法：因为m要最大，所以每次Xi只能乘以一个质因子。若不然可以得到一个更短的链。
3 // 先求出所有的质因子，所有质因子的排列除以重复的次数就是这种链的个数.
4
5 #include <iostream>
6 #include <math.h>
7
8 using namespace std;
9
10 __int64 p[172];
11 // 因子数目最多是20个
12 int e[21];
13 int cnt;
14 __int64 factor[21];
15
16 // naive method
17 void prime2()
18 {
19 int i,j,k,flag;
20 p[0]=2;
21 cnt=1;
22 for(i=3;i<1024;i++){
23 flag=0;
24 j=sqrt(1.0*i);
25
26 for(k=2;k<=j;k++){
27 if(i%k==0) {flag=1;break;}
28 }
29 if(!flag) p[cnt++]=i;
30 }
31 }
32
33 void prime()
34 {
35 int i,j,flag;
36 p[0]=2;
37 p[1]=3;
38 cnt=2;
39 for(i=5;i<=1024;i+=2){
40 flag=0;
41 for(j=1;p[j]*p[j]<=i;j++){
42 if(i%p[j]==0) {flag=1;break;}
43 }
44 if(!flag) p[cnt++]=i;
45 }
46 }
47
48 // 先质因子分解，再求组合的个数
49 void solve(__int64 a)
50 {
51 // j统计所有质因子的个数，k统计不同质因子个数
52 int i,j=0,flag,l=0;
53 memset(e,0,sizeof(e));
54 // 用1024以内的素数分解a，注意到a<=2^20，a最多含有一个超过1024的质因子
55 // a=p1^e1*p2^e2**pk^ek*ps^es，其中只有ps是大于1024的素数，且es只能为0或1
56 for(i=0;i<cnt && a>1;i++){
57 flag=0;
58 while(a%p[i]==0){
59 flag=1;
60 e[l]++;
61 a/=p[i];
62 j++;
63 }
64 if(flag==1) l++;
65 }
66 // 若此时a!=1则a一定是素数
67 if(a!=1) {j++;e[l++]=1;}
68 __int64 res = factor[j];
69 for(i=0;i<l;i++){
70 if(e[i]!=0) res/=factor[e[i]];
71 }
72 printf("%d %I64d\n",j,res);
73 }
74
75 int main()
76 {
77 prime1();
78 //cnt=172;
79 // 阶乘
80 factor[0]=1;
81 for(__int64 i=1;i<21;i++) factor[i]=factor[i-1]*i;
82 __int64 a;
83 while(scanf("%I64d",&a)!=EOF){
84 solve(a);
85 }
86
87 return 1;
88 }
89
|