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).
The 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.
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
#include
#include
#include
#include
#include
#include
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
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
>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
还有一种方法：
#include
#include
#include
#include
#include
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