本文主要是介绍UVa10375，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述很简单,就是求两个组合数的商.可是数字范围很大,肯定不能直接计算.
因此要用到唯一分解定理,即将结果全部表示为素因子的幂的形式.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>
#include<cmath>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e4+5;
bool check[MAXN];
int prime[MAXN];
int cnt[MAXN];
int tot;
int p,q,r,s;void creat_prime()
{tot=0;for(int i=2;i<MAXN;i++){if(!check[i]) prime[tot++]=i;for(int j=0;j<tot && prime[j]*i<MAXN ;j++){check[prime[j]*i]=true;if(i%prime[j]==0) break;}}
}void add(int l,int r,int d)
{for(int i=l;i<=r;i++){int t=i;for(int j=0;j<tot;j++){while(t%prime[j]==0){cnt[j]+=d;t/=prime[j];}if(t==1) break;}}
}int main()
{creat_prime();while(~scanf("%d%d%d%d",&p,&q,&r,&s)){memset(cnt,0,sizeof(cnt));add(1,r-s,1);add(q+1,p,1);add(1,p-q,-1);add(s+1,r,-1);double ans=1.0;for(int i=0;i<tot;i++){ans*=pow(prime[i],cnt[i]);}printf("%.5f\n",ans);}return 0;
}这篇关于UVa10375的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
