poj 2992 Divisors

解题思路：不妨设 C(n,k) 的标准分解式为 C(n,k)=p₁^a₁p₂^a₂···pt^at .^_.

① n! 中素数 p 的指数为 np(n,p)=[n/p]+[n/p²]+...+[n/p^k], 其中p^k≤n<p^k+1 .

由于 C(n,k)=n!/(k!·(n-k)!), 故 C(n,k) 中素数 p_i 的指数 a_i=np(n,p_i)- np(k,p_i)- np(n-k,p_i);

②若正整数 n 的标准分解式为 n=p_1^b^₁p_2^b^₂···ps_^bs, 则 n 的因子数为 (b₁+1)(b₂+1)···(bs+1) .

由于 C(n,k)=p₁^a₁p₂^a₂···pt^at , 故 C(n,k) 的因子数为 (a₁+1)(a₂+1)···(at+1) .

 1 ///////////////////////////////////////////////////////////////////////////
 2 //problem_id: poj 2992
 3 //user_id: SCNU20102200088
 4 ///////////////////////////////////////////////////////////////////////////
 5 
 6 #include <algorithm>
 7 #include <iostream>
 8 #include <iterator>
 9 #include <iomanip>
10 #include <cstring>
11 #include <cstdlib>
12 #include <string>
13 #include <vector>
14 #include <cstdio>
15 #include <cctype>
16 #include <cmath>
17 #include <queue>
18 #include <stack>
19 #include <list>
20 #include <set>
21 #include <map>
22 using namespace std;
23 
24 ///////////////////////////////////////////////////////////////////////////
25 typedef long long LL;
26 const double PI=acos(-1.0);
27 ///////////////////////////////////////////////////////////////////////////
28 
29 ///////////////////////////////////////////////////////////////////////////
30 //Add Code:
31 bool isp[435];
32 int num=0,p[100];
33 
34 void prim(){  //素数筛法,筛选出1-431的素数
35     int i,j;
36     memset(isp,1,sizeof(isp));
37     for(i=2;i*i<435;i++){
38         if(isp[i]){
39             for(j=i*i;j<435;j+=i) isp[j]=0;
40         }
41     }
42     for(i=2;i<435;i++){
43         if(isp[i]) p[num++]=i;
44     }
45 }
46 
47 int np(int n,int p){  //求n!中素数p的指数
48     int t=p,count=0;
49     while(t<=n){
50         count+=n/t;
51         t*=p;
52     }
53     return count;
54 }
55 ///////////////////////////////////////////////////////////////////////////
56 
57 int main(){
58     ///////////////////////////////////////////////////////////////////////
59     //Add code:
60     prim();
61     int n,k,i;
62     LL C[435][435];
63     memset(C,-1,sizeof(C));
64     while(scanf("%d%d",&n,&k)!=EOF){
65         if(C[n][k]>-1){
66             printf("%I64d
",C[n][k]);
67             continue;
68         }
69         C[n][k]=1;
70         for(i=0;i<num && p[i]<=n;i++){  //求C[n][k]的因子数
71             C[n][k]*=np(n,p[i])-np(n-k,p[i])-np(k,p[i])+1;
72         }
73         printf("%I64d
",C[n][k]);
74     }
75     ///////////////////////////////////////////////////////////////////////
76     return 0;
77 }
78 
79 ///////////////////////////////////////////////////////////////////////////
80 /*
81 Testcase:
82 Input:
83 5 1
84 6 3
85 10 4
86 Output:
87 2
88 6
89 16
90 */
91 ///////////////////////////////////////////////////////////////////////////