UVa 10375 Choose and divide【唯一分解定理】

题意：已知C(m,n)=m!/(n!(m-n)!),求C(p,q)/C(r,s)

因为C(p,q)/C(r,s)可以化简成(p!(r-s)!(s!))/(q!(p-q)!r!)

然后就可以用唯一分解定理，算出这个式子中分别的素数的个数再乘起来就可以了

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=10005;
17 
18 int vis[maxn];
19 int e[maxn];
20 vector<int> primes;
21 
22 void is(){
23     memset(vis,0,sizeof(vis));
24     vis[0]=1;vis[1]=1;
25     for(int i=2;i<=10005;i++)
26      for(int j=i*2;j<=10005;j+=i) vis[j]=1;
27      
28 }
29 
30 void add_integer(int n,int d){
31     for(int i=0;i<primes.size();i++){
32         while(n%primes[i]==0){
33             n=n/primes[i];
34             e[i]+=d;
35         }
36         if(n==1) break;
37     }
38 }
39 
40 void add_factorial(int n,int d){
41     for(int i=1;i<=n;i++)
42     add_integer(i,d);
43 }
44 
45 int main(){
46     int p,q,r,s;
47 //    freopen("in.txt","r",stdin);
48 //    freopen("out.txt","w",stdout);
49     
50     is();    
51     for(int i=0;i<=10000;i++){
52         if(vis[i]==0) primes.push_back(i);
53     }
54     
55     while(cin>>p>>q>>r>>s){
56         memset(e,0,sizeof(e));
57         add_factorial(p,1);
58         add_factorial(q,-1);
59         add_factorial(p-q,-1);
60         add_factorial(r,-1);
61         add_factorial(s,1);
62         add_factorial(r-s,1);
63         
64         double ans=1;
65         for(int i=0;i<primes.size();i++){
66             ans*=pow(primes[i],e[i]);
67     //        printf("%.5lf
",ans);    
68         }
69         
70         printf("%.5lf
",ans);        
71     }
72     return 0;
73 }

View Code