• 这一题根据定义计算即可：

$$ C_a^b = \frac{a!}{b! \times (a-b)!} $$

• 我们需要实现一个高精度乘法和一个高精度除法。这样的写法运行效率比较低，另外也比较难写。

• 我们可以考虑对$C_a^b$进行质因数分解，假设：

$$ C_a^b = p_1^{\alpha_1} \times p_2^{\alpha_2} \times … \times p_k^{\alpha_k} $$

这样我们只需要写高精度乘法即可。

• 如何计算每个质因子出现的次数呢？我们发现$C_a^b$是一个阶乘除以另外两个阶乘，因此，我们可以分别求出这三个阶乘的质因数分解，然后将对应质因数的幂次相减即可。此时问题就转换成了如何求解阶乘的质因数分解，对应题目：AcWing 197. 阶乘分解。

• 阶乘的质因数分解：$n!$所有的质因子一定是小于等于n的，否则如果存在大于n的质因子，说明该质因子一定是某几个数相乘得到的，违反质数的定义。

（1）求出1~n中所有的质数，可以使用线性法筛质数，可以参考：网址；

（2）枚举某个质数p，则其出现的次数为：
$$ \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + ...... $$
该方法求阶乘$n!$的质因数分解的时间复杂度大约为$O(n)$，因为1~n中大约有$\frac{n}{log(n)}$个质数，求每个质数出现次数计算大约为$log(n)$的，相乘得到阶乘质因数分解时间复杂度大约为$O(n)$的。

• 本题的解题步骤是：

（1）使用线性筛法筛出1~a之间的所有质数，时间复杂度$O(a)$；

（2）根据 $C_a^b$ 定义计算其质因数分解结果，时间复杂度$O(a)$；

（3）高精度乘法计算最终结果。

代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 5010;

int primes[N], cnt;
bool st[N];  // 该数据是否被筛掉
int sum[N];  // sum[i]代表primes[i]在C(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;
        }
    }
}

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() {

    int a, b;
    cin >> a >> b;

    // (1) 使用线性筛法筛出1~a之间的所有质数
    get_primes(a);
    // (2) 根据 C(a, b) 定义计算其质因数分解结果
    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }
    // (3) 高精度乘法计算最终结果
    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--) printf("%d", res[i]);
    puts("");

    return 0;
}