模板:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
int primes[N],cnt; bool not_prime[N]; void Init() { for(int i=2;i<N;i++) { if(!not_prime[i]) { primes[cnt++]=i; for(int j=i+i;j<N;j+=i) { not_prime[j]=true; } } } } LL Get(LL n,LL p)//n!中因子p的个数 { LL s=0; LL op=p; while(p<=n) { s+=n/p; p*=op;//对p^k处理 } return s; } int sum[N];//分解质因数的数量 int C(int n,int k,int r[N]) { memset(sum,0,sizeof(sum)); for(int i=0;i<cnt;i++)//枚举质因数 { sum[i]=Get(n,primes[i])-Get(k,primes[i])-Get(n-k,primes[i]); } //此时已经获得了组合数的全部质因数,乘起来就是结果 }View Code
分解质因数求组合数结合高精度例题:
https://www.acwing.com/problem/content/1317/
标签:组合,int,算法,分解,质因数,AcWing From: https://www.cnblogs.com/ydUESTC/p/16769222.html