首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。