題目描述很簡單,就是求兩個組合數的商.可是數字范圍很大,肯定不能直接計算.

因此要用到唯一分解定理,即將結果全部表示為素因子的冪的形式.

#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;
}