| UVA - 10375 |
Choose and divide
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4053 | Accepted: 1318 |
Description
The binomial coefficient C(m,n) is defined as
m!
C(m,n) = --------
n!(m-n)!
Given four natural numbers p, q, r, and s, compute the the result of dividing C(p,q) by C(r,s).
Input
Input consists of a sequence of lines. Each line contains four non-negative integer numbers giving values for p, q, r, and s, respectively, separated by a single space. All the numbers will be smaller than 10,000 with p>=q and r>=s.
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
Sample Output
0.12587
505606.46055
1.28223
0.48996
2.00000
3.99960
Source
唯一分解定理
太诡异了，uva AC
poj一直TLE，连白书的标解都WA
//
// main.cpp
// poj2613
//
// Created by Candy on 10/20/16.
// Copyright ? 2016 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e4+;
int p,q,r,s;
int prime[N],cnt=,e[N],vis[N];
void era(int n){
int m=sqrt(n)+;
for(int i=;i<=m;i++) if(!vis[i])
for(int j=i*i;j<=n;j+=i) vis[j]=;
for(int i=;i<=n;i++) if(!vis[i]) prime[++cnt]=i;
}
inline void mul(int x,int d){//x^d
for(int i=;i<=cnt&&x!=;i++)
while(x%prime[i]==){
x/=prime[i];
e[i]+=d;
}
}
void fac(int x,int d){//printf("%d %d\n",x,d);
for(int i=;i<=x;i++) mul(i,d);
}
inline int fastPow(int a,int b){
int ans=;
for(;b;b>>=,a*=a)
if(b&) ans*=a;
return ans;
}
int main(int argc, const char * argv[]){
era();//cout<<"p";
while(scanf("%d%d%d%d",&p,&q,&r,&s)!=EOF){
memset(e,,sizeof(e));
fac(p,);
fac(q,-);
fac(p-q,-);
fac(r,-);
fac(s,);
fac(r-s,);
double ans=;
for(int i=;i<=cnt;i++){
if(e[i]>) ans*=(double)fastPow(prime[i],e[i]);
else if(e[i]<) ans/=(double)fastPow(prime[i],-e[i]);
// ans*=pow(prime[i],e[i]);
}
printf("%.5f\n",ans);
} return ;
}