UVA

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

Waterloo local 1999.10.02

唯一分解定理

太诡异了，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+5;
int p,q,r,s;
int prime[N],cnt=0,e[N],vis[N];
void era(int n){
    int m=sqrt(n)+1;
    for(int i=2;i<=m;i++) if(!vis[i])
        for(int j=i*i;j<=n;j+=i) vis[j]=1;
    for(int i=2;i<=n;i++) if(!vis[i]) prime[++cnt]=i;
}
inline void mul(int x,int d){//x^d
    for(int i=1;i<=cnt&&x!=1;i++)
        while(x%prime[i]==0){
            x/=prime[i];
            e[i]+=d;
        }
}
void fac(int x,int d){//printf("%d %d
",x,d);
    for(int i=1;i<=x;i++) mul(i,d);
}
inline int fastPow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a*=a)
        if(b&1) ans*=a;
    return ans;
}
int main(int argc, const char * argv[]){
    era(10000);//cout<<"p";
    while(scanf("%d%d%d%d",&p,&q,&r,&s)!=EOF){
        memset(e,0,sizeof(e));
        fac(p,1);
        fac(q,-1);
        fac(p-q,-1);
        fac(r,-1);
        fac(s,1);
        fac(r-s,1);
        double ans=1;
        for(int i=1;i<=cnt;i++){
            if(e[i]>0) ans*=(double)fastPow(prime[i],e[i]);
            else if(e[i]<0) ans/=(double)fastPow(prime[i],-e[i]);
//            ans*=pow(prime[i],e[i]);
        }
        printf("%.5f
",ans);
    }
 
    return 0;
}