首页 > 代码库 > UVa10375 Choose and divide

UVa10375 Choose and divide

http://vjudge.net/problem/UVA-10375

 

组合数除以组合数……

唯一分解定理将每个乘数和除数分解质因数,统计每个质因数的使用次数(乘一次+1,除一次-1),所有数分解完毕以后挨个计算每个质因数……

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=12000; 9 int pri[mxn],cnt=0;10 bool vis[mxn];11 int num[mxn];12 void Pri(){13     int m=sqrt(mxn);14     cnt=0;int i,j;15     for(i=2;i<=m;i++)16         if(!vis[i])    for(j=i*i;j<mxn;j+=i)vis[j]=1;17     for(i=2;i<mxn;i++)if(!vis[i])pri[++cnt]=i;18 }19 void addint(int n,int v){//n-要分解的数字 v-正负 20     int i,j;21     for(i=1;i<=cnt;i++){22         while(n%pri[i]==0){23             n/=pri[i];24             num[i]+=v;25         }26         if(n==1)return;27     }28     return;29 }30 void solve(int n,int v){31     for(int i=1;i<=n;i++)32         addint(i,v);33     return;34 }35 int main(){36     Pri();37     int p,q,r,s;int mx;38     while(scanf("%d%d%d%d",&p,&q,&r,&s)!=EOF){39         memset(num,0,sizeof num);40         solve(p,1);41         solve(q,-1);42         solve(p-q,-1);43         solve(r,-1);44         solve(s,1);45         solve(r-s,1);46         mx=max(p,r);47         double ans=1;48         for(int i=1;i<=cnt;i++){49             ans*=pow(pri[i],num[i]);50         }51         printf("%.5f\n",ans);52     }53     return 0;54 }

 

UVa10375 Choose and divide