DLKKILL

DLKKILL's world

UVA - 10375 - Choose and divide (唯一分解定理)

题目链接:UVA – 10375 

题目大意:C(m, n) = m! /(m − n)! n!

                  求C(p, q)/C(r,s)

题目分析:利用唯一分解定理,把每一个数分解成用素数的指数次方形式。

                  最后利用pow()函数求值即可

给出代码:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
const int maxn= 10000+10;
const int MOD=10001;
int e[maxn];
int prime[maxn];
vector<int> nums;
void get_primes()
{
    prime[0]=prime[1]=1;
    for(int i=2;i<=10000+2;i++)
    {
        if(prime[i]==0)
        {
            nums.push_back(i);
            for(int j=i*i;j<=10000+2;j+=i)
            {
                prime[j]=1;
            }
        }
    }
    return;
}
void add_interger(int n,int d)
{
    for(int i=0;i<nums.size();i++)
    {
        while(n%nums[i]==0)
        {
            n/=nums[i];
            e[i]+=d;
        }
        if(n==1)
            break;
    }
}
void add_factorial(int n,int d)
{
    for(int i=1;i<=n;i++)
    {
        add_interger(i,d);
    }
}
int main()
{
    int p,q,r,s;
    get_primes();
    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;
        for(int i=0;i<nums.size();i++)
        {
            ans*=pow(nums[i],e[i]);
        }
        printf("%.5lf\n",ans);
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注