例10-3 uva10375（唯一分解定理）

题意：已知C(m,n) = m!/(n!(m-n)!),已知p，q，r，s，求C(p,q)/C(r,s)

思路：

全部分解成质因子，相乘则加，除则减

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N =10001;
vector<int>prime;
int pri[N];
int num[N];
void getprime()
{
    memset(pri,1,sizeof(pri));
    for(int i = 2; i <= N; i++)
    {
        if(pri[i])
        {
            prime.push_back(i);
            for(int j = i+i; j <= N; j+=i)
                pri[j] = 0;
        }
    }
}

void add_factorial(int n,int d)   //
{
    for(int i = 1;i <= n;i++)
    {
        int tt = i;
        for(int j = 0;j < prime.size();j++)
        {
            while(tt % prime[j] == 0)
            {
                num[j]+=d;
                tt /= prime[j];
            }
            if(tt == 1)
                break;
        }
    }
}

int main()
{
    int p,q,r,s;
    getprime();
    while(scanf("%d%d%d%d",&p,&q,&r,&s) != EOF)
    {
        memset(num,0,sizeof(num));
        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 < prime.size();i++)
        {
            ans *= pow(prime[i],num[i]);
        }
        printf("%.5lf
",ans);
    }
    return 0;
}