UVa 10375 选择与除法(唯一分解定理)

https://vjudge.net/problem/UVA-10375

题意:

输入整数p,q,r,s,计算C(p,q)/C(r,s)。

思路:

先打个素数表,然后用一个数组e来保存每个素数所对应的指数,最后相乘。

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
using namespace std; const int maxn=+; int primes[maxn];
int e[maxn];
int vis[maxn];
int p,q,r,s;
int cnt; void get_primes()
{
memset(vis,,sizeof(vis));
int m=sqrt(maxn+0.5);
for(int i=;i<=m;++i) if(!vis[i])
for(int j=i*i;j<=maxn;j+=i) vis[j]=;
cnt=;
for(int i=;i<=maxn;++i){
if(!vis[i])
primes[cnt++]=i;
}
} void add_integer(int n,int d )
{
for(int i=;i<cnt;i++)
{
while(n%primes[i]==)
{
n/=primes[i];
e[i]+=d;
}
if(n==) break;
}
} void update_e(int n,int d)
{
for(int i=;i<=n;i++)
add_integer(i,d);
} int main()
{
//freopen("D:\\input.txt","r",stdin);
get_primes();
while(~scanf("%d%d%d%d",&p,&q,&r,&s))
{
memset(e,,sizeof(e));
update_e(p,);
update_e(q,-);
update_e(p-q,-);
update_e(s,);
update_e(r-s,);
update_e(r,-);
double ans=;
for(int i=;i<cnt;i++)
{
ans*=pow(primes[i],e[i]);
}
printf("%.5f\n",ans);
}
return ;
}
上一篇:反射那些基础-Class


下一篇:spring cloud(四)熔断器Hystrix