AcWing 888. 求组合数IV
原题链接
简单
作者:
大笔筒
,
2022-03-20 17:00:43
,
所有人可见
,
阅读 247
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5010;
int primes[N],cnt;
bool st[N];
int sum[N];
int a,b;
vector<int> ans;
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(st[i]==false) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int get_cnt(int x1,int p)
{
int x=x1;
int res=0;
while(x!=0)
{
res+=x/p;
x/=p;
}
return res;
}
vector<int> mul(int p)
{
vector<int> res;
int t=0;
for(int i=0;i<ans.size();i++)
{
t+=ans[i]*p;
res.push_back(t%10);
t/=10;
}
while(t!=0)
{
res.push_back(t%10);
t/=10;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin>>a>>b;
get_primes(a);
ans.push_back(1);
for(int i=0;i<cnt;i++)
{
int p=primes[i];
sum[i]=get_cnt(a,p)-get_cnt(b,p)-get_cnt(a-b,p);
}
for(int i=0;i<cnt;i++)
{
for(int j=0;j<sum[i];j++)
ans=mul(primes[i]);
}
for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
return 0;
}
大佬,请问为什么sum[i]是>=0的呢?有没有可能出现小于0的情况,该怎么证明呢
不会的。
因为根据组合公式:C=
$$ \frac{a!}{b!(a-b)!} \quad $$
,C一定大于等于零
又因为任何数可以分成x=
$$ p1^{x1}p2^{x2}…∗pk^{xk} $$
(p=prime)
所以C也可以分解成上述形式,我们的sum[]是记录p的次方的
当然p的次方是>=0,根据初中数学幂的定理,次方=p在a!中的次数-p在b!中的次数-p在(a-b)!中的次数,即为
get_cnt(a,p)-get_cnt(b,p)-get_cnt(a-b,p)
所以 次方=上述代码的计算
次方>=0,sum[i]>=0