UVA 10375 Choose and divide（唯一分解定理）

// // main.cpp // Richard // // Created by 邵金杰 on 16/8/15. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int maxn=10000+10; int is_prime[maxn],primes[maxn],e[maxn]; int cnt; void get_prime() { cnt=0; memset(is_prime,1,sizeof(is_prime)); for(int i=2;i<maxn;i++) { if(is_prime[i]) primes[cnt++]=i; for(int j=0;j<cnt&&i*primes[j]<maxn;j++) { is_prime[i*primes[j]]=0; if(i%primes[j]==0) break; } } } void add_e(int n,int d) { for(int i=0;i<cnt;i++) { while(n%primes[i]==0) { e[i]+=d; n/=primes[i]; } if(n==1) break; } } void add_factorial(int n,int d) { for(int i=1;i<=n;i++) { add_e(i,d); } } int main() { int p,q,r,s; get_prime(); while(scanf("%d%d%d%d",&p,&q,&r,&s)!=EOF) { 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<cnt;i++) { ans*=pow(primes[i],e[i]); } printf("%.5f\n",ans); } return 0; }