欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-02 12:00:08
...

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

#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
using namespace std;
const int MAX_N=100000000;
int prime[MAX_N];//素数表
bool is_prime[MAX_N+1];
int n;
//返回n以内的素数的个数
int sieve(int n)
{
    int p=0;
    for(int i=0;i<=n;i++)is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])
        {
            prime[p++]=i;//素数打表
            for(int j=2*i;j<=n;j+=i)is_prime[j]=false;//去掉已有素数的倍数
        }
    }
    return p;
}
int e[10005];
void add_num(int m,int d)
{
    if(m==0)return;
    for(int i=0;i<n;i++)
    {
        while(m%prime[i]==0){
            m/=prime[i];e[prime[i]]+=d;
        }
    }
}
void add_factorial(int num,int d)
{
    for(int i=1;i<=num;i++)add_num(i,d);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    int p,q,s,r;
    n=sieve(10005);

    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<n;i++)
        {
            ans*=pow(prime[i],e[prime[i]]);
        }
        printf("%.5f\n",ans);
    }
}