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

今天药忘吃喽~ 2023-07-08 02:37 11阅读 0赞

> 原题链接：[10375 - Choose and divide][]

**题意：** 已知  C ( m , n ) = m ! / ( n ! ∗ ( m − n ! ) ) C(m,n)=m! / (n!\*(m-n!)) C(m,n)=m!/(n!∗(m−n!)) ，输入整数  p , q , r , s ( p > = q , r > = s , p , q , r , s < = 10000 ) p,q,r,s (p>=q,r>=s,p,q,r,s<=10000) p,q,r,s(p>=q,r>=s,p,q,r,s<=10000) ，计算  C ( p , q ) / C ( r , s ) C(p,q)/C(r,s) C(p,q)/C(r,s) 。输出保证不超过 1 0 8 10^8 108，保留  5 5 5 位小数。

**思路：** 直接暴力肯定会超过范围，可用唯一分解定理求解，通过将其分解为指数幂次相乘的形式即可。

**Code：**

#include <iostream>
    #include <cstring>
    #include <cmath>
    #include <iomanip>
    using namespace std;
    const int N=1e4+10;
    int p,q,r,s,cnt;
    int isPrime[N],Prime[N],e[N];
    void getPrime(){ 
        for(int i=2;i<=sqrt(N);i++){ 
            if(!isPrime[i]){ 
                for(int j=i*i;j<=N;j+=i)
                    isPrime[j]=1;
            }
        }
        cnt=0;
        for(int i=2;i<=N;i++){ 
            if(!isPrime[i])
                Prime[cnt++]=i;
        }
    }
    void add_integer(int n,int d){ 
        for(int i=0;i<cnt;i++){ 
            while(n%Prime[i]==0){ 
                n/=Prime[i];
                e[i]+=d;
            }
            if(n==1)    break;
        }
    }
    void add_factorial(int n,int d){ 
        for(int i=1;i<=n;i++)
            add_integer(i,d);
    }
    int main(){ 
        getPrime();
        while(cin>>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<=N;i++)
                ans*=pow(Prime[i],e[i]);
            cout<<fixed<<setprecision(5)<<ans<<endl;
        }
        return 0;
    }

[10375 - Choose and divide]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1316