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

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

#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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。