這道題從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
|