首页 > 代码库 > UVA 10375 Choose and divide(数论)
UVA 10375 Choose and divide(数论)
The binomial coefficient C(m,n) is defined as Given four natural numbers p, q, r, and s, compute the the result of dividingC(p,q) by C(r,s).
m! C(m,n) = -------- n!(m-n)!
The Input
Input consists of a sequence of lines. Each line contains four non-negative integer numbers giving values forp, q, r, and s, respectively, separated by a single space. All the numbers will be smaller than 10,000 withp>=q and r>=s.The Output
For each line of input, print a single line containing a real number with 5 digits of precision in the fraction, giving the number as described above. You may assume the result is not greater than 100,000,000.Sample Input
10 5 14 9 93 45 84 59 145 95 143 92 995 487 996 488 2000 1000 1999 999 9998 4999 9996 4998
Output for Sample Input
0.12587 505606.46055 1.28223 0.48996 2.00000 3.99960
唯一分解定理:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> #include<vector> #include<cmath> typedef long long LL; typedef unsigned long long ULL; using namespace std; const int maxn=10005; int e[maxn]; int p,q,r,s; int visit[maxn]; vector<int>prime; void is_prime(int n) { int m=sqrt(n+0.5); memset(visit,0,sizeof(visit)); for(int i=2;i<=m;i++) { for(int j=i*i;j<=n;j+=i) visit[j]=1; } } void get_prime(int n) { for(int i=2;i<=n;i++) { if(!visit[i]) prime.push_back(i); } } void add_integer(int n,int d) { for(int i=0;i<prime.size();i++) { while(n%prime[i]==0) { n/=prime[i]; e[i]+=d; } if(n==1) break; } } void add_factorial(int n,int d) { for(int i=1;i<=n;i++) add_integer(i,d); } int main() { is_prime(maxn-1); get_prime(maxn-1); while(cin>>p>>q>>r>>s) { memset(e,0,sizeof(e)); add_factorial(p,1); add_factorial(q,-1); add_factorial(p-q,-1); add_factorial(r,-1); add_factorial(s,1); add_factorial(r-s,1); double ans=1.0; for(int i=0;i<prime.size();i++) ans*=pow(prime[i],e[i]); printf("%.5f\n",ans); } return 0; }
还有一种方法:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> typedef long long LL; typedef unsigned long long ULL; using namespace std; int p,q,r,s; int main() { while(~scanf("%d%d%d%d",&p,&q,&r,&s)) { if(p-q<q)//q和p-q中较大值的阶乘和p的阶乘消去 q=p-q; if(r-s<s) s=r-s; double ans=1.0; for(int i=1;i<=q||i<=s;i++) { if(i<=q) ans=ans*(p-q+i)/i; if(i<=s) ans=ans/(r-s+i)*i; } printf("%.5f\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。