【题目来源】
AcWing：888. 求组合数 IV - AcWing题库
【题目描述】
输入 \(a,b\)，求 \(C_a^b\) 的值。
注意结果可能很大，需要使用高精度计算。
【输入】
共一行，包含两个整数 \(a\) 和 \(b\)。
【输出】
共一行，输出 \(C_a^b\) 的值。
【输入样例】
5 3
【输出样例】
10
【算法标签】
《AcWing 888 求组合数IV》 #组合数学# #组合计数# #高精度#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 5005; // 质数表大小
int primes[N], cnt; // primes存储质数，cnt是质数个数
bool st[N]; // 筛法标记数组
int sum[N]; // 存储每个质因子的指数// 线性筛法求1~n的所有质数
void get_primes(int n)
{for (int i = 2; i <= n; i++){if (!st[i]) // 如果i是质数{primes[cnt++] = i; // 加入质数表}// 用当前已得到的质数筛掉合数for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true; // 标记合数if (i % primes[j] == 0) // 如果primes[j]是i的最小质因数{break; // 保证每个合数只被最小的质因数筛掉}}}
}// 计算n!中质因子p的指数（勒让德定理）
int get(int n, int p)
{int res = 0; // 指数结果// 勒让德公式：n!中质因子p的指数 = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ...while (n){res += n / p; // 计算⌊n/p⌋n /= p; // 继续计算下一项}return res;
}// 高精度乘法：大整数A乘以小整数b
vector<int> mul(vector<int> &A, int b)
{vector<int> C; // 存储结果int t = 0; // 进位for (int i = 0; i < A.size() || t; i++) // 遍历A的每一位或还有进位{if (i < A.size()) // 如果A还有位数{t += A[i] * b; // 当前位乘以b加上进位}C.push_back(t % 10); // 取个位t /= 10; // 计算进位}// 去掉前导0，但保留最后一位0（如果结果就是0）while (C.size() > 1 && C.back() == 0){C.pop_back();}return C;
}int main()
{int a, b; // 输入C(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]; // 当前质数// 勒让德公式计算C(a,b)中质因子p的指数// C(a,b) = a! / (b! * (a-b)!)// 指数 = 在a!中的指数 - 在b!中的指数 - 在(a-b)!中的指数sum[i] = get(a, p) - get(b, p) - get(a - b, p);}// 3. 用高精度乘法计算结果vector<int> res; // 存储高精度结果，低位在前res.push_back(1); // 初始化为1// 遍历所有质因子for (int i = 0; i < cnt; i++){int p = primes[i]; // 当前质数int exp = sum[i]; // 质因子p的指数// 将p乘exp次for (int j = 0; j < exp; j++){res = mul(res, p);}}// 4. 输出结果（从高位到低位）for (int i = res.size() - 1; i >= 0; i--){cout << res[i];}cout << endl;return 0;
}
【运行结果】
5 3
10