74.Acwing基础课第888题-简单-求组合数Ⅳ
题目描述
\(输入a，b，求 C^b_a的值\)。
输入格式
\(共一行，包含两个整数 a 和 b\)。
输出格式
\(共一行，输出 C^b_a的值\)。
数据范围
\(1≤b≤a≤5000\)
输入样例：
5 3
输出样例：
10
代码：
// 包含基础输入输出、算法、向量容器头文件（vector用于存储高精度数）
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;// 常量定义：N=5010，支持计算C(a,b)中a≤5000的组合数
const int N = 5010;// 全局变量：
// primes[]：存储1~a范围内的所有质数
// cnt：质数的个数
// sum[]：存储每个质数在组合数中的指数（C(a,b) = ∏(p^sum[p])）
// st[]：筛法标记数组（true表示非质数）
int primes[N], cnt;
int sum[N];
bool st[N];// 线性筛（欧拉筛）函数：筛选出1~n范围内的所有质数，时间复杂度O(n)
// 优势：每个数仅被其最小质因子筛一次，效率高于普通筛法
void get_primes(int n)
{// 遍历2~n的所有数for (int i = 2; i <= n; i ++ ){// 若未被标记，说明是质数，加入primes数组if (!st[i]) primes[cnt ++ ] = i;// 用当前质数筛除合数for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true; // 标记primes[j]*i为非质数// 若i能被primes[j]整除，说明primes[j]是i的最小质因子，退出循环（避免重复筛）if (i % primes[j] == 0) break;}}
}// 计算n!中质因子p的指数（公式：n/p + n/p² + n/p³ + ... 直到p^k > n）
int get(int n, int p)
{int res = 0; // 存储指数总和while (n){res += n / p; // 累加n/p（p的倍数个数）n /= p; // 计算更高次幂的倍数个数（p², p³...）}return res;
}// 高精度乘法函数：将高精度数a（逆序存储）与低精度数b相乘，返回结果
// 例如：a=[1,2]（表示21），b=2 → 结果=[2,4]（表示42）
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; // 更新进位（十位及以上）}// 处理剩余进位（如t=123，需依次存储3、2、1）while (t){c.push_back(t % 10);t /= 10;}return c;
}int main()
{int a, b; // a：总数；b：选取数（计算C(a,b)）cin >> a >> b;// 步骤1：筛选出1~a范围内的所有质数get_primes(a);// 步骤2：计算每个质数在C(a,b)中的指数// 组合数公式：C(a,b) = a!/(b!*(a-b)!) → 质因子p的指数 = get(a,p) - get(b,p) - get(a-b,p)for (int i = 0; i < cnt; i ++ ){int p = primes[i]; // 当前质数sum[i] = get(a, p) - get(a - b, p) - get(b, p);}// 步骤3：高精度乘法计算最终结果（初始为1）vector<int> res;res.push_back(1); // 初始值1（逆序存储：[1]表示1）// 遍历每个质数，按指数乘到结果中for (int i = 0; i < cnt; i ++ )for (int j = 0; j < sum[i]; j ++ )res = mul(res, primes[i]);// 步骤4：输出结果（逆序存储，需从后往前遍历）for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);puts(""); // 换行return 0;
}