UVa 10375 选择与除法（唯一分解定理）

题意：

输入整数p，q，r，s，计算C（p，q）/C（r，s）。

思路：

先打个素数表，然后用一个数组e来保存每个素数所对应的指数，最后相乘。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 
11 const int maxn=10000+5;
12 
13 int primes[maxn];
14 int e[maxn];
15 int vis[maxn];
16 int p,q,r,s;
17 int cnt;
18 
19 void get_primes()
20 {
21     memset(vis,0,sizeof(vis));
22     int m=sqrt(maxn+0.5);
23     for(int i=2;i<=m;++i)  if(!vis[i])
24         for(int j=i*i;j<=maxn;j+=i) vis[j]=1;
25     cnt=0;
26     for(int i=2;i<=maxn;++i){
27         if(!vis[i])
28             primes[cnt++]=i;
29     }
30 }
31 
32 void add_integer(int n,int d )
33 {
34     for(int i=0;i<cnt;i++)
35         {
36         while(n%primes[i]==0)
37         {
38             n/=primes[i];
39             e[i]+=d;
40         }
41         if(n==1) break;
42     }
43 }
44 
45 void update_e(int n,int d)
46 {
47     for(int i=1;i<=n;i++)
48         add_integer(i,d);
49 }
50 
51 int main()
52 {
53     //freopen("D:\input.txt","r",stdin);
54     get_primes();
55     while(~scanf("%d%d%d%d",&p,&q,&r,&s))
56     {
57         memset(e,0,sizeof(e));
58         update_e(p,1);
59         update_e(q,-1);
60         update_e(p-q,-1);
61         update_e(s,1);
62         update_e(r-s,1);
63         update_e(r,-1);
64         double ans=1;
65         for(int i=0;i<cnt;i++)
66         {
67             ans*=pow(primes[i],e[i]);
68         }
69         printf("%.5f
",ans);
70     }
71     return 0;
72 }