先說(shuō)一個(gè)定理：
若正整數(shù)n可分解為p1^a1*p1^a2*...*pk^ak
其中pi為兩兩不同的素?cái)?shù),ai為對(duì)應(yīng)指數(shù)
n的約數(shù)個(gè)數(shù)為(1+a1)*(1+a2)*....*(1+ak)
如180=2*2*3*3*5=2^2*3^2*5
180的約數(shù)個(gè)數(shù)為(1+2)*(1+2)*(1+1)=18個(gè)。
若求A/B的約數(shù)個(gè)數(shù)，A可分解為p1^a1*p2^a2*...*pk^ak，B可分解為q1^b1*q1^b2*...*qk^bk,則A/B的約數(shù)個(gè)數(shù) 為(a1-b1+1)*(a2-b2+1)*(a3-b3+1)...*(ak-bk+1).
然后說(shuō)N的階乘：
例如:20!
1.先求出20以內(nèi)的素?cái)?shù),(2,3,5,7,11,13,17,19)
2.再求各個(gè)素?cái)?shù)的階數(shù)
e(2)=[20/2]+[20/4]+[20/8]+[20/16]=18;
e(3)=[20/3]+[20/9]=8;
e(5)=[20/5]=4;
...
e(19)=[20/19]=1;
所以
20!=2^18*3^8*5^4*...*19^1
解釋：
2、4、6、8、10、12、14、16、18、20能被2整除
4、8、12、16、20能被4整除（即被2除一次后還能被2整除）
8、16能被8整除（即被2除兩次后還能被2整除）
16能被16整除（即被2除三次后還能被2整除）
這樣就得到了2的階。其它可以依次遞推。
所以在求N的階乘質(zhì)數(shù)因數(shù)個(gè)數(shù)時(shí)，從最小的質(zhì)數(shù)開(kāi)始，
1 int cal(int n, int p) {
2 if(n < p) return 0;
3 else return n / p + cal(n / p, p);
4 }
其中P是質(zhì)數(shù)，則該函數(shù)返回的就是N的階乘中可以表達(dá)成質(zhì)數(shù)P的指數(shù)的最大值。原理如上。
TOJ 2308的AC代碼：
1 #include<iostream>
2
3 #include<cmath>
4
5 #define N 90
6
7 #define M 450
8
9 using namespace std;
10
11 int p[M+2]={0};
12
13 int prime[N+2],l,q,t=1; //求前90個(gè)素?cái)?shù)
14
15 void getprime(int n)
16
17 {
18
19 for(l=2;l<n;l++)
20
21 {
22
23 if(!p[l])
24
25 {
26
27 for(q=l+l;q<n;q+=l)
28
29 {
30
31 p[q]=1;
32
33 }
34
35 prime[t]=l;t++;
36
37 }
38
39 }
40
41 }
42
43 int cal(int n,int m) //求N的階乘含質(zhì)因數(shù)M的次數(shù)
44
45 {
46 if(m>n)
47
48 return 0;
49
50 else
51
52 return n/m+cal(n/m,m);
53
54 }
55 int main()
56 {
57 int i,j,k,n;
58
59 long long m;
60
61 getprime(M);
62
63 while(cin>>n>>k)
64
65 {
66 if(2*k>n) k=n-k;
67
68 for(i=1,m=1;prime[i]<=n,i<t;i++)
69
70 m*=(cal(n,prime[i])-cal(k,prime[i])-cal(n-k,prime[i])+1);
71
72 cout<<m<<endl;
73
74 }
75 }