本文主要是介绍例题 10-3 选择和除法(Choose and Divide, UVa10375),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题链接:https://vjudge.net/problem/UVA-10375
分类:基础数论
备注:唯一分解定理
要想到指数的直接应用。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e8+5;
int p,q,r,s,e[maxn],vis[maxn];
vector<int>primes;
void init(){int m=sqrt(maxn+0.5);for(int i=2;i<=m;++i){if(!vis[i]){primes.push_back(i);for(int j=i*i;j<maxn;j+=i){vis[j]=1;}}}
}
void add_integer(int n,int d){for(int i=0;i<primes.size();++i){while(n%primes[i]==0){n/=primes[i];e[i]+=d;}if(n==1)break;}
}
void add_factorial(int n,int d){for(int i=1;i<=n;++i){add_integer(i,d);}
}
int main(void){
// freopen("in.txt","r",stdin);init();while(~scanf("%d%d%d%d",&p,&q,&r,&s)){memset(e,0, sizeof(int)*primes.size());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<primes.size();++i){ans*=pow(primes[i],e[i]);}printf("%.5lf\n",ans);}return 0;
}
这篇关于例题 10-3 选择和除法(Choose and Divide, UVa10375)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!