888. 求组合数 IV

利用公式$C^b_a=\frac{a!}{b!×(a-b)!}$求组合数步骤:

①筛质数：求出$1$~$a$中的所有质数；
②求次数：将$\frac{a!}{b!×(a-b)!}$分解质因数，求出每个质数的次数；
③高精度乘法：将所有质因数相乘。

①

void get_primes(int n)//线性素数筛
{
    for(int i=2; i<=n; i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=n/i; j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

②

求a!中质数p的次数res依据：
$res=\left\lfloor\frac{a}{p}\right\rfloor+\left\lfloor\frac{a}{p^2}\right\rfloor+\left\lfloor\frac{a}{p^3}\right\rfloor+… 直到p^n>=a$

$\left\lfloor\frac{a}{p}\right\rfloor表示a!中p的倍数的个数$；
$\left\lfloor\frac{a}{p^2}\right\rfloor表示a!中p^2的倍数的个数，每个倍数包含两次p，在前面的式子中被res加了一次，还剩一次$；
$\left\lfloor\frac{a}{p^3}\right\rfloor表示a!中p^3的倍数的个数，每个倍数包含三次p，在前面的式子中被res加了两次，还剩一次$；
…
对应代码如下：

int get(int n, int p)//求n!中p的次数
{
    int res=0;
    while(n)//循环第一次res加的是p的倍数，第二次加的是p^2的倍数，第三次加的是p^3的倍数...
    {
        res+=n/p;
        n/=p;
    }
    return res;
}

for(int i=0; i<cnt; i++)//第二步：将a!/b!/(a-b)!分解质因数，求出a!/b!/(a-b)!中每个质数的次数
{
    int p=primes[i];
    sum[i]=get(a, p)-get(b, p)-get(a-b, p);
}

③

vector<int> mul(vector<int> a, int b)//高精度乘以低精度
{
    vector<int> c;
    int t=0;
    for(int i=0; i<a.size()||t; i++)
    {
        if(i<a.size()) t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }

    while(c.size() && c.back()==0) c.pop_back();

    return c;
}

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]);//将所有质因子相乘

代码

#include <bits/stdc++.h>
using namespace std;

const int N=5005;

int primes[N], cnt;//存质数
int sum[N];//质数的次数
bool st[N];//标记这个数是否被筛掉

void get_primes(int n)//线性素数筛
{
    for(int i=2; i<=n; i++)
    {
        if(!st[i]) 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(int n, int p)//求n!中p的次数
{
    int res=0;
    while(n)//循环第一次res加的是p的倍数，第二次加的是p^2的倍数，第三次加的是p^3的倍数...
    {
        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()||t; i++)
    {
        if(i<a.size()) t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }

    while(c.size() && c.back()==0) c.pop_back();

    return c;
}

int main()
{
    int a, b;
    cin>>a>>b;

    get_primes(a);//第一步：筛出1~a中的质数

    for(int i=0; i<cnt; i++)//第二步：将a!/b!/(a-b)!分解质因数，求出a!/b!/(a-b)!中每个质数的次数
    {
        int p=primes[i];
        sum[i]=get(a, p)-get(b, p)-get(a-b, p);
    }

    vector<int> res;
    res.push_back(1);//进行乘法前，初始值为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--) printf("%d", res[i]);

    return 0;
}