PKU 2992给出n跟k，求有多少个约数。
思路如下：
要知道一个数n约数的个数，首先要知道n的质因子分解：
接着就可以按下式来算所有约数的个数了：
*(e_{2}+1)*\dots*(e_{l}+1))
其次，要知道一个数n的质因子分解，要打素数表，然后对每个小于n的素数p试除，看n含有多少个p的因子。
题目是要求n!/(k!(n-k)!的约数个数，如果直接算出n!/(k!(n-k)!会很麻烦，可以分别对n!, k!, (n-k)!做如上分解，然后对于同一个底
，用n在
的指数
减去k对应的指数及(n-k)对应的指数，就得到n!/(k!(n-k)!在底
的指数了。
可以用递推的方法来求n!的质因子分解，具体见代码。
1 // pku 2992 质因子分解
2 #include <iostream>
3 #include <math.h>
4 using namespace std;
5
6 int p[90]; // 素数表
7 int pn;
8 int e[432][90]; // 对应素数的指数，质因子分解
9 int n,k;
10
11 // 筛法复杂度为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 }