poj 2992

大意：求（n，k）的因子个数

解题思路：（n，k） = n！/（k！(n-k)!）

任意一个数都可以用其质因子来表示 eg： 26 = 2^1 * 13^1; 240 = 2^4 * 3 *5;

即 x = p1^q1 * p2^2 *p3*q3 ....... 其因子的个数为（q1+1）*（q2+1）*（q3+1）。。。。

所以把 n! , k!, (n-k)! 中的公共因子删去，就得到的（n，k）的结果

 1 #include <iostream>
 2 #include<math.h>
 3 using namespace std;
 4 long long res[437][437];
 5 int prime[437];
 6 void get_prime(){
 7    // cout<<"---------->"<<endl;
 8     int m = (int)sqrt(435+0.5);
 9     prime[0] = prime[1] =1;
10     for(int i=2;i<=m;i++){
11         if(!prime[i]){
12            // cout<<i<<endl;
13             for(int j=i*i;j<=435;j+=i)
14                 prime[j] =1;
15         }
16     }
17 
18 }
19 
20 void solve(){
21 
22     int i,j,n;
23     for(int i=2;i<=435;i++){//到i的阶乘为止，其所有质因子的个数
24         for(int j=0;j<i;j++)
25             res[i][j] = res[i-1][j];//只需再求i即可，，前面的一样。。
26         n =i;
27         for(j=2;j<=435&&n>1;j++){
28             if(!prime[j]){
29                 while(n%j==0){//注意是%j 而不是%prime[j]。。
30                     res[i][j]++;
31                     n = n/j;
32                 }
33             }
34         }
35         if(n>1)
36             res[i][n]++;
37     }
38 }
39 int main()
40 {
41     get_prime();
42     solve();
43     /*for(int i=1;i<=10;i++)
44         if(!prime[i])
45             cout<<i<<endl;*/
46     int n,k;
47     while(cin>>n>>k){
48         long long sum =1;
49         for(int i=2;i<=n;i++)
50             if(!prime[i])
51                 sum *=(res[n][i]-res[k][i]-res[n-k][i]+1);//不要忘记+1.
52         cout<<sum<<endl;
53     }
54     return 0;
55 }