poj 1306

求C(n,m)，n m 最大为100，任何一个数都可以表示成质因子的幂的乘积 x = p1 ^ a1 * p2 ^ a2 ~~~pn ^ an，这样对 C(n,m) = n! / ((n - m)! * m!)，对分别对 n,m,(n - m)分解质因子，然后用质因子的幂数想减，最后得到的（p1 ^ sum1 * p2 ^ sum2 ~~~pn ^ sumn），就为结果。

View Code

 1 typedef long long ll;
 2 const int N = 101;
 3 int prime[N];
 4 bool vis[N];
 5 int sumn[N],summ[N],sum[N];
 6 int num;
 7 void is_prime()
 8 {
 9     int i,j;
10     for(i = 2; i <= N; i++)
11     {
12         if(!vis[i]) prime[num ++] = i;
13         for(j = 2; j*i <= N; j++)
14         {
15             if(vis[i * j]) continue;
16             vis[i * j] = true;
17         }
18     }
19 }
20 void cal(int x,int flag)
21 {
22     int i;
23     for(i = 0; i < num; i++)
24     {
25         if(x == 1) break;
26         if(x % prime[i] == 0)
27         {
28             int sum = 0;
29             while(x % prime[i] == 0)
30             {
31                 sum ++;
32                 x /= prime[i];
33             }
34             if(!flag) sumn[prime[i]] += sum;
35             else summ[prime[i]] += sum;
36         }
37     }
38 }
39 int main()
40 {
41     num = 0;
42     int i;
43     is_prime();
44     int n,m;
45     while(~scanf("%d%d",&n,&m))
46     {
47         if(!n && !m) break;
48         _clr(sumn,0);
49         _clr(summ,0);
50         for(i = 1; i <= n; i++) cal(i,0);
51         for(i = 1; i <= m; i++) cal(i,1);
52         for(i = 1; i <= n - m; i++) cal(i,1);
53         ll sum = 1;
54         for(i = 0; i <= 100; i++)
55         {
56             int k = sumn[i] - summ[i];
57             while(k--) sum *= i;
58         }
59         printf("%d things taken %d at a time is %I64d exactly.\n",n,m,sum);
60     }
61     return 0;
62 }