PKU 2992給出n跟k，求有多少個(gè)約數(shù)。
思路如下：
要知道一個(gè)數(shù)n約數(shù)的個(gè)數(shù)，首先要知道n的質(zhì)因子分解：
接著就可以按下式來算所有約數(shù)的個(gè)數(shù)了：
*(e_{2}+1)*\dots*(e_{l}+1))
其次，要知道一個(gè)數(shù)n的質(zhì)因子分解，要打素?cái)?shù)表，然后對(duì)每個(gè)小于n的素?cái)?shù)p試除，看n含有多少個(gè)p的因子。
題目是要求n!/(k!(n-k)!的約數(shù)個(gè)數(shù)，如果直接算出n!/(k!(n-k)!會(huì)很麻煩，可以分別對(duì)n!, k!, (n-k)!做如上分解，然后對(duì)于同一個(gè)底
，用n在
的指數(shù)
減去k對(duì)應(yīng)的指數(shù)及(n-k)對(duì)應(yīng)的指數(shù)，就得到n!/(k!(n-k)!在底
的指數(shù)了。
可以用遞推的方法來求n!的質(zhì)因子分解，具體見代碼。
1 // pku 2992 質(zhì)因子分解
2 #include <iostream>
3 #include <math.h>
4 using namespace std;
5
6 int p[90]; // 素?cái)?shù)表
7 int pn;
8 int e[432][90]; // 對(duì)應(yīng)素?cái)?shù)的指數(shù)，質(zhì)因子分解
9 int n,k;
10
11 // 篩法復(fù)雜度為O(n^2)，下面的試除法只要sigma(sqrt(i)),2<=i<=n
12 void prime()
13 {
14 int i,j;
15 pn=0;
16 p[pn++]=2;
17 for(i=3;i<=431;i++){
18 int up=(int)sqrt(i);
19 int flag=0;
20 for(j=2;j<=up && !flag;j++){
21 if(i%j==0) flag=1;
22 }
23 if(flag==0) p[pn++]=i;
24 }
25 //printf("cnt=%d\n",pn);
26 //for(i=0;i<pn;i++) printf("%d ",p[i]);
27 return;
28 }
29
30 void fact()
31 {
32 int i,j;
33 for(i=2;i<=431;i++){
34 int a=i;
35 //printf("%d:",a);
36 for(j=0;j<pn;j++){
37 while(a>1 && a%p[j]==0) {e[i][j]++;a/=p[j];}
38 //printf("%d ",e[i][j]);
39 }
40 //printf("\n");
41 }
42 for(i=3;i<=431;i++){
43 for(j=0;j<pn;j++) e[i][j]+=e[i-1][j];
44 }
45 }
46
47 /*
48 void divide(int a)
49 {
50 int i;
51 for(i=0;i<pn;i++){
52 while(a%p[i]==0) {e[e]--;a/=p[i];}
53 }
54 }
55 */
56
57 int main()
58 {
59 //freopen("in.txt","r",stdin);
60 int i,j;
61 prime();
62 fact();
63 while(scanf("%d%d",&n,&k)!=EOF){
64 //for(n=0;n<=431;n++){
65 //for(k=0;k<n;k++){
66 __int64 sum=1;
67 for(i=0;i<pn;i++) sum*=(1+(e[n][i]-e[k][i]-e[n-k][i]));
68 printf("%I64d\n",sum);
69 //}
70 //printf("1\n");
71 }
72 return 1;
73 }