UVA 10375 Choose and divide【唯一分解定理】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：求C(p,q)/C(r,s)，4个数均小于10000，答案不大于10^8

思路：根据答案的范围猜测，不需要使用高精度。根据唯一分解定理，每一个数都可以分解成若干素数相乘。先求出10000以内的所有素数，用a数组表示唯一分解式中个素数的指数，求出每个分子部分的素因子，并且相应的素数的指数加一。分母则减一。最后求解唯一分解式的值。

#include<stdio.h>

#include<string.h>

#include<math.h>

const int N=1e4+;

int pr[N],p[N],a[N],cnt;

void init(){

    for(int i=;i<N;i++){

        if(!p[i])    pr[++cnt]=i;

        for(int j=;j<=cnt&&i*pr[j]<N;i++){

            p[pr[j]*i]=;

            if(i%pr[j]==)    break;

        }

    }

}

void er(int n,int d){

    for(int i=;i<=cnt;i++){

        if(n%pr[i]==){

            while(n%pr[i]==){

                a[i]+=d;

                n/=pr[i];

            }

        }

        if(n==)    break;

    }

}

void add(int n,int d){

    for(int i=;i<=n;i++){

        er(i,d);

    }

}

int main(){

    init();

    int p,q,r,s;

    while(~scanf("%d%d%d%d",&p,&q,&r,&s)){

        memset(a,,sizeof(a));

        add(p,);add(q,-);add(p-q,-);

        add(r,-);add(s,);add(r-s,);

        double ans=1.0;

        for(int i=;i<=cnt;i++)

            ans*=pow(pr[i],a[i]);

        printf("%.5f\n",ans);

    }

    return ;

}