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 4998Sample Output
0.12587 505606.46055 1.28223 0.48996 2.00000 3.99960Source
Waterloo local 1999.10.02
题意非常明了：
求C(P,Q)/C(R,S)
原来直接除就可以过了。我的思路有非常的非主流了一回。。。
我害怕阶乘的大小超过了double的承受范围所以跑去写了个把阶乘分解为质因子的程序
然后再根据质因子的积的形式表示下的阶乘来一个一个的除，还好是1A要不然可真的要跑去跳楼了。。
我的代码：
#include<stdio.h> #include<string.h> int prime[10000]; bool flag[10000]; int cnt=0; void init() { int i,j; memset(flag,0,sizeof(flag)); for(i=2;i<10000;i++) { if(!flag[i]) { prime[cnt++]=i; for(j=i*i;j<10000;j=j+i) flag[j]=true; } } } int min(int a,int b) { if(a>b) return b; else return a; } void slove(int s,int e,int ph[]) { int i,j,dive; for(i=s;i<=e;i++) { dive=i; for(j=0;j<cnt;j++) { if(dive%prime[j]==0) { ph[prime[j]]++; dive=dive/prime[j]; while(dive%prime[j]==0) { ph[prime[j]]++; dive=dive/prime[j]; } } if(dive==1) break; } } } int main() { int p,q,r,s,i,j; int ph1[10000],ph2[10000],ph3[10000],ph4[10000]; int p1[10000],p2[10000]; double ans; init(); while(scanf("%d%d%d%d",&p,&q,&r,&s)!=EOF) { q=min(p-q,q); s=min(r-s,s); memset(ph1,0,sizeof(ph1)); memset(ph2,0,sizeof(ph2)); memset(ph3,0,sizeof(ph3)); memset(ph4,0,sizeof(ph4)); slove(p-q+1,p,ph1); slove(1,s,ph2); slove(1,q,ph3); slove(r-s+1,r,ph4); for(i=0;i<10000;i++) { p1[i]=ph1[i]+ph2[i]; p2[i]=ph3[i]+ph4[i]; } ans=1; for(i=0;i<10000;i++) { if(p1[i]>p2[i]) { for(j=1;j<=p1[i]-p2[i];j++) ans=ans*i; } else { for(j=1;j<=p2[i]-p1[i];j++) ans=ans/i; } } printf("%.5lf/n",ans); } return 0; }