AcWing 888. 求组合数 IV
原题链接
简单
作者:
minux
,
2020-05-01 00:17:14
,
所有人可见
,
阅读 593
#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int primes[N], cnt;
int sum[N];
bool vis[N];
// 线性质数筛
void getPrimes(int n){
for(int i=2; i<=n; ++i){
if(!vis[i]) primes[cnt++]=i;
for(int j=0; primes[j]<=n/i; ++j){
vis[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int get(int n, int p){
int res=0;
while(n){
res+=n/p;
n/=p;
}
return res;
}
vector<int> mul(vector<int> a, int b){
vector<int> c;
int t=0;
for(int i=0; i<a.size(); ++i){
t+=a[i]*b;
c.push_back(t%10);
t/=10;
}
while(t){
c.push_back(t%10);
t/=10;
}
return c;
}
int main(){
memset(primes, 0x00, sizeof primes);
memset(vis, 0x00, sizeof vis);
cnt=0;
// 高精度计算
int a,b;
cin>>a>>b;
getPrimes(a);
for(int i=0; i<cnt; ++i){
int p=primes[i];
sum[i]=get(a, p)-get(b, p)-get(a-b, p);
}
vector<int> res;
res.push_back(1);
for(int i=0; i<cnt; ++i){
for(int j=0; j<sum[i]; ++j)
res=mul(res, primes[i]);
}
for(int i=res.size()-1; i>=0; --i) cout<<res[i];
puts("");
return 0;
}