Choose and divide (唯一分解定理)
程序员文章站
2022-06-02 11:52:48
...
题目链接
题目大意:给出p,q,s和r, 计算C(p, q) / C(s, r), 公式题目已经给出。
为一分解定理:任何一个大于1的自然数N,那么N可以用 某些素数的次方乘积 表示,类似于每自然数可以用二进制数表示。
题解:统计分子,分母中所有素数因子的贡献3^(3,2,0,-1,-3......) ,遍历所有素数的贡献即是答案。注意不要分母,分子分别算再除,会有溢出的问题。
#include<bits/stdc++.h> using namespace std; int p,q,r,s; const int N=1e4+5; bool mark[N]; int prim[N]; int cnt; void initial() { cnt=0; for (int i=2 ; i<N ; ++i) { if (!mark[i]) prim[cnt++]=i; for (int j=0 ; j<cnt && i*prim[j]<N ; ++j) { mark[i*prim[j]]=1; if (!(i%prim[j])) break; } } } int num[10005]; void go(int a,int b) { for(int j=2;j<=a;j++) { int n=j; for(int i=0;n>1&&i<cnt;i++) { while(n%prim[i]==0) { num[prim[i]]+=b; n/=prim[i]; } } } } int main() { initial(); while(cin>>p>>q>>r>>s) { memset(num,0,sizeof(num)); go(p,1); go(s,1); go(r-s,1); go(q,-1); go(r,-1); go(p-q,-1); double ans=1.0; for(int ii=0;ii<cnt;ii++) { int i=prim[ii]; ans*=pow(i,num[i]);//i^num[i] } printf("%.5f\n",ans); } } //10 5 14 9 //93 45 84 59 //145 95 143 92 //995 487 996 488 //2000 1000 1999 999 //9998 4999 9996 4998
上一篇: 昆山周边最适合亲子自驾游地点