**给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。
例如，我们从6767开始，将得到
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。
输入给出一个 (0,104) 区间内的正整数 N。
如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。**
#include <cstdio>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) { // 递减排序 cmp
return a > b;
}
void to_array(int n, int num[]) { // 将 n 的每一位存到 num 数组中
for (int i = 0; i < 4; i++) {
num[i] = n % 10;
n /= 10;
}
}
int to_number(int num[]) { // 将 num 数组转换为数字
int sum = 0;
for (int i = 0; i < 4; i++) {
sum = sum * 10 + num[i];
}
return sum;
}
int main() {
int n, MIN, MAX;
int num[5]; // 声明数组，用于存储数字的每一位（实际使用4位，多一位用于安全）
scanf("%d", &n);
while (1) {
to_array(n, num); // 将 n 转换为数组
sort(num, num + 4); // 对 num 数组从小到大排序
MIN = to_number(num); // 获取最小值
sort(num, num + 4, cmp); // 对 num 数组从大到小排序
MAX = to_number(num); // 获取最大值
n = MAX - MIN; // 计算差值
printf("%04d - %04d = %04d\n", MAX, MIN, n);
if (n == 0 || n == 6174) break; // 如果差值为0或6174则退出循环
}
return 0;
}![[Pasted image 20251109131713.png]]
48 ÷ 18 = 2 余 12
18 ÷ 12 = 1 余 6
12 ÷ 6 = 2 余 0
∴ gcd(48, 18) = 6int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}或者
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}![[Pasted image 20251109133511.png]]
int lcm(int a, int b) {
// 使用公式：LCM(a, b) = a * b / GCD(a, b)
// 先除后乘防止溢出
return a / gcd(a, b) * b;
}防止溢出：
int lcm(int a, int b) {
if (a == 0 || b == 0) return 0;
// 防止溢出：先除后乘
int g = gcd(a, b);
return (a / g) * b; // 确保除法无余数
}给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。
子数组 是数组中一个连续的非空序列。
数组的最大公因数 是能整除数组中所有元素的最大整数。
示例 1：
**输入：**nums = [9,3,1,2,6,3], k = 3
**输出：**4
**解释：**nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
枚举所有子数组，计算每个子数组的 GCD，并检查是否等于 k 来实现。为了提高效率，可以在枚举时进行优化(剪枝)：如果当前 GCD 已经小于 k 且 k>0（继续扩展子数组，GCD 只会更小或保持不变），或者当前 GCD 不为 0 且 k=0，则提前终止内层循环。
PS：对于任意子数组
nums[i..j]，扩展为nums[i..j+1]时：
gcd(nums[i..j+1]) = gcd(gcd(nums[i..j]), nums[j+1])由于 gcd(a, b) 总是整除 a，所以：
gcd(nums[i..j+1]) ≤ gcd(nums[i..j])
即 GCD 序列是单调不增的。
因此，一旦 g < k，后续的 GCD 值只会 ≤ g，永远不可能 = k。
主函数 subarrayGCD：
- 遍历每个起始索引
i。 - 对于每个起始索引
i，初始化g为nums[i]，然后遍历从i到数组末尾的子数组。 - 更新当前子数组的 GCD
g，如果g等于k，则增加计数。 - 根据
k的值进行优化：如果k>0且g小于k，或者k=0且g不为0，则提前终止内层循环。 代码块(暴力)
class Solution {
public:
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
int subarrayGCD(vector<int>& nums, int k) {
int n = nums.size();
int count = 0;
for (int i = 0; i < n; i++) {
int g = nums[i];
for (int j = i; j < n; j++) {
g = gcd(g, nums[j]);
if (g == k) {
count++;
}
// 剪枝：如果当前 GCD 已经不可能等于 k，提前终止循环
if (k > 0 && g < k) {
break;
}
if (k == 0 && g != 0) {
break;
}
}
}
return count;
}
};LCM 序列具有单调不减的性质，这与 GCD 的单调不增性质形成对比。
class Solution {
public:
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
int lcm(int a, int b){
if (a == 0 || b == 0) return 0;
return a / gcd(a, b) * b;
}
int subarrayLCM(vector<int>& nums, int k) {
int n = nums.size();
int count = 0;
for(int i = 0; i < n; i++){
//初始化
int l = nums[i];
for(int j = i; j < n; j++){
l = lcm(l, nums[j]);
if(l > k){
break;
}
if(l == k){
count++;
}
}
}
return count;
}
};为了防溢出，可以使用longlong
总结一下这两道题：
- 这两道题几乎一模一样，区别在于，GCD是单调不增的，LCM是单调不减的（用于剪枝）
- 其次，GCD和LCM函数必须掌握！！先写这两个函数
- 主函数：主要思路是找一个”引子“，开始遍历。从第一个元素开始，把这个元素设为引子。然后遍历剩下的节点
- 剪枝：体现在两方面。 一个是以g（l）为引子，遍历剩下的元素时重新定义g（l），使得g为遍历过的元素的最大公约数/最小公倍数。 另一个是利用GCD，LCM的性质进行剪枝（单调不增，单调不减）
struct Fraction {
int up, down; // 分子、分母
};规则：
- 分母为非负数，分数为负时只让分子为负
- 分数为0时，分子为0，分母为1
- 分子分母互质（没有除了1以外的公约数）
Fraction reduction(Fraction result) {
if(result.down < 0) {
result.up = -result.up;
result.down = -result.down;
}
if(result.up == 0) {
result.down = 1;
} else {
int d = gcd(abs(result.up), abs(result.down));
result.up /= d;
result.down /= d;
}
return result;
}加法：
result = (f1.up*f2.down + f2.up*f1.down) / (f1.down*f2.down)减法：
result = (f1.up*f2.down - f2.up*f1.down) / (f1.down*f2.down)乘法：
result = (f1.up*f2.up) / (f1.down*f2.down)除法：
result = (f1.up*f2.down) / (f1.down*f2.up)注意： 除法要判断除数是否为0
- 先化简分数
- 分母为1 → 输出整数
- 假分数 → 输出带分数形式
- 真分数 → 原样输出
给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。
这个结果应该是不可约分的分数，即 最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。
示例 :
输入: expression = "-1/2+1/2"
输出: "0/1"
isdigit ：C++ 标准库中的一个函数，用于判断一个字符是否是数字字符。
代码块:(longlong防溢出)
class Solution {
public:
string fractionAddition(string expression) {
// 初始化结果为 0/1
long long up = 0, down = 1;
int i = 0, n = expression.size();
while (i < n) {
// 读取符号
int sign = 1;
if (expression[i] == '+' || expression[i] == '-') {
if (expression[i] == '-') sign = -1;
i++;
}
// 读取分子
long long num = 0;
while (i < n && isdigit(expression[i])) {
num = num * 10 + (expression[i] - '0');//可能是多位数
i++;
}
num *= sign;
// 跳过 '/'
i++;
// 读取分母
long long den = 0;
while (i < n && isdigit(expression[i])) {
den = den * 10 + (expression[i] - '0');
i++;
}
// 通分相加: a/b + c/d = (a*d + c*b)/(b*d)
up = up * den + num * down;
down = down * den;
// 每次计算后化简，防止溢出
long long g = gcd(abs(up), down);
up /= g;
down /= g;
}
return to_string(up) + "/" + to_string(down);
}
private:
// 最大公约数函数
long long gcd(long long a, long long b) {
while (b != 0) {
long long temp = b;
b = a % b;
a = temp;
}
return a;
}
};给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于 104 。
注意，如果分数可以表示为有限长度的字符串，则 必须 返回它。
示例 ：
**输入：**numerator = 1, denominator = 2
输出："0.5"
代码块：
llabs计算 long long 类型的绝对值。
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
string result;
// 处理符号
if ((numerator < 0) ^ (denominator < 0)) {
result += '-';
}
// 转换为正数处理，使用long long防止溢出
long long num = llabs((long long)numerator);
long long den = llabs((long long)denominator);
// 整数部分
result += to_string(num / den);
num %= den;
if (num == 0) return result;
// 小数部分
result += '.';
unordered_map<long long, int> remainderPos;
while (num != 0) {
// 如果当前余数已经出现过，说明开始循环
if (remainderPos.find(num) != remainderPos.end()) {
result.insert(remainderPos[num], "(");
result += ')';
break;
}
// 记录当前余数的位置
remainderPos[num] = result.size();
// 计算下一位小数
num *= 10;
result += to_string(num / den);
num %= den;
}
return result;
}
};- 素数定义：只能被1和自身整除的大于1的自然数
- 关键优化：只需检查到 √n 即可，因为如果n有因数，必有一个 ≤ √n
方法一：开根号法（推荐）
sqrt : 计算n的平方根，并向下取整（转换为整数）。接受一个double类型的参数，并返回double类型的平方根。
bool isPrime(int n) {
if (n <= 1) return false;
int sqr = (int)sqrt(1.0 * n);
for (int i = 2; i <= sqr; i++) {
if (n % i == 0) return false;
}
return true;
}方法二：平方判断法
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}- 时间复杂度：O(n√n)
- 适合 n ≤ 10⁵
void findPrime() {
for (int i = 1; i < maxn; i++) {
if (isPrime(i)) {
prime[pNum++] = i;
p[i] = true;
}
}
}- 时间复杂度：O(nloglogn)
- 核心思想：用素数标记掉所有倍数
void findPrime() {
for (int i = 2; i < maxn; i++) {
if (!p[i]) { // i是素数
prime[pNum++] = i;//将素数i存入prime数组
for (int j = i + i; j < maxn; j += i) {
p[j] = true; // 标记倍数为非素数
}
}
}
}我写的：
class Solution {
public:
bool isPrimes(int n){
if(n <= 1) return false;
int sqr = sqrt(1.0 * n);
for(int i = 2; i <= sqr; i++){
if(n % i == 0) return false;
}
return true;
}
int countPrimes(int n) {
int ans = 0;
for(int i = 1; i < n; i++){
if(isPrimes(i)) ans++;
}
return ans;
}
};超出了时间限制。 怎么优化？ 使用埃拉托斯特尼筛法
- 基础版本（从
i+i开始） - 优化版本（从
i*i开始）
class Solution {
public:
int countPrimes(int n) {
if (n <= 2) return 0; // 小于2没有素数
// 创建标记数组，初始都认为是素数
vector<bool> isPrime(n, true);
isPrime[0] = false; // 0不是素数
isPrime[1] = false; // 1不是素数
// 核心：埃拉托斯特尼筛法
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) { // 如果i是素数
// 标记i的所有倍数为非素数
// 从i*i开始，因为所有小于 i² 的 i 的倍数都已经被更小的素数标记过了
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
// 统计结果
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}
};提交了 i+i 的解法后，系统说："Time Limit Exceeded"
质数5叹了口气："早告诉你要从 i*i 开始优化，你偏不信！"
这些图片内容是关于质因子分解**的算法讲解和代码实现，主要来自《算法笔记》这本书。我来为你系统性地梳理和讲解：
质因子分解：将一个正整数分解为若干个质数（素数）的乘积形式。
- 连乘形式：
180 = 2 × 2 × 3 × 3 × 5 - 指数形式：
180 = 2² × 3² × 5¹注意：1不是素数，没有质因子。
struct factor {
int x, cnt; // x为质因子，cnt为其个数（指数）
} fac[10];为什么数组大小是10？
因为 2×3×5×7×11×13×17×19×23×29 已经超过int范围，所以对于int范围内的数，最多有10个不同的质因子。
对于正整数n，它的质因子要么：
- 全部 ≤ √n
- 或者只有一个 > √n，其余都 ≤ √n 作法
- 枚举 1~√n 范围内的所有质因子p
- 判断 p是否是n的因子：
- 如果是：记录该因子，并不断除以p，统计出现次数
- 如果不是：跳过
- 检查 如果最后n > 1，说明n本身就是一个质因子
#include <cstdio>
#include <cmath>
const int maxn = 100010;
// 判断素数函数
bool is_prime(int n) {
if(n == 1) return false;
int sqr = (int)sqrt(1.0 * n);
for(int i = 2; i <= sqr; i++) {
if(n % i == 0) return false;
}
return true;
}
// 素数表
int prime[maxn], pNum = 0;
void Find_Prime() {
for(int i = 1; i < maxn; i++) {
if(is_prime(i)) {
prime[pNum++] = i;
}
}
}
// 质因子结构体
struct factor {
int x, cnt;
} fac[10];
int main() {
Find_Prime(); // 务必调用！
int n, num = 0;
scanf("%d", &n);
if(n == 1) printf("1=1"); // 特判1的情况
else {
printf("%d=", n);
int sqr = (int)sqrt(1.0 * n);
// 枚举√n以内的质因子
for(int i = 0; i < pNum && prime[i] <= sqr; i++) {
if(n % prime[i] == 0) {
fac[num].x = prime[i];
fac[num].cnt = 0;
while(n % prime[i] == 0) {
fac[num].cnt++;
n /= prime[i];
}
num++;
}
if(n == 1) break; // 提前退出
}
// 处理大于√n的质因子
if(n != 1) {
fac[num].x = n;
fac[num++].cnt = 1;
}
// 输出结果
for(int i = 0; i < num; i++) {
if(i > 0) printf("*");
printf("%d", fac[i].x);
if(fac[i].cnt > 1) printf("^%d", fac[i].cnt);
}
}
return 0;
}- 忘记调用
Find_Prime()函数 - 循环条件写错（如
i ≤ maxn应为i < maxn） - 没有处理大于√n的质因子
- 在循环条件中直接计算sqrt(n)，应该提前存储
求因子个数：
如果 n = p₁ᵉ¹ × p₂ᵉ² × ... × pₖᵉᵏ，则：
因子个数 = (e₁+1) × (e₂+1) × ... × (eₖ+1)
求因子和：
因子和 = (1+p₁+p₁²+...+p₁ᵉ¹) × (1+p₂+p₂²+...+p₂ᵉ²) × ...
= ∏[(pᵢᵉⁱ⁺¹ - 1)/(pᵢ - 1)]
这些图片内容是关于大整数运算（高精度运算） 的详细讲解，我来为你系统性地梳理：
当整数位数超过基本数据类型（如int、long long）的范围时（比如1000位数），就需要用特殊方法处理。
memset 是 C/C++ 中的一个内存设置函数，用于将一块内存区域的每个字节都设置为特定的值。
void *memset(void *str, int c, size_t n)struct bign { // big number的缩写
int d[1000]; // 存储每一位数字
int len; // 记录数字长度
// 构造函数，自动初始化
bign() {
memset(d, 0, sizeof(d));// 将d数组的所有字节设为0
len = 0;
}
};重要特点：
- 顺位存储：整数的高位存储在数组的高位，低位存储在数组的低位
- 例如：235813 →
d[0]=3, d[1]=1, d[2]=8, d[3]=5, d[4]=3, d[5]=2
数组索引: 0 1 2 3 4
存储内容: 5 4 3 2 1
数字意义: 个位 十位 百位 千位 万位bign change(char str[]) {
// 将字符串形式的数字转换为bign结构体
// 例如："12345" → bign{ [5,4,3,2,1], len=5 }
bign a;//创建bign对象
a.len = strlen(str);//设置长度
for(int i = 0; i < a.len; i++) {
// 逆序存储：字符串是正序，要转为逆序存储
a.d[i] = str[a.len - i - 1] - '0';
}
return a;
}为什么要逆序储存？
字符串索引: 0 1 2 3 4
字符内容: '1','2','3','4','5'
数字意义: 万位 千位 百位 十位 个位int compare(bign a, bign b) {
if(a.len > b.len) return 1; // a大
else if(a.len < b.len) return -1; // a小
else {
for(int i = a.len - 1; i >= 0; i--) {
if(a.d[i] > b.d[i]) return 1;
else if(a.d[i] < b.d[i]) return -1;
}
return 0; // 相等
}
} 147
+ 65
------
212
代码块：
bign add(bign a, bign b) {
bign c;
int carry = 0; // 进位标志，初始为0
for(int i = 0; i < a.len || i < b.len; i++) {
int temp = a.d[i] + b.d[i] + carry;//当前位相加 + 进位
c.d[c.len++] = temp % 10; // 取个位作为结果
carry = temp / 10; // 计算新的进位
}
if(carry != 0) {
c.d[c.len++] = carry;
}
return c;
} 147
- 65
------
82
代码块：
bign sub(bign a, bign b) {
bign c;
for(int i = 0; i < a.len || i < b.len; i++) {
if(a.d[i] < b.d[i]) { // 不够减
a.d[i+1]--; // 向高位借1
a.d[i] += 10; // 当前位加10
}
c.d[c.len++] = a.d[i] - b.d[i];
}
// 去除高位多余的0
while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
c.len--;
}
return c;
}注意：使用前要先比较大小，如果a<b，需要交换并输出负号。
147
× 35
------
735
441
------
5145
代码块：
bign multi(bign a, int b) {
bign c;
int carry = 0;
for(int i = 0; i < a.len; i++) {
int temp = a.d[i] * b + carry;
c.d[c.len++] = temp % 10;
carry = temp / 10;
}
// 处理剩余进位（可能有多位）
while(carry != 0) {
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}代码块：
bign divide(bign a, int b, int& r) { // r为余数（引用传递）
bign c;
c.len = a.len; // 商与被除数位数一一对应
r = 0; // 余数初始化为0
for(int i = a.len - 1; i >= 0; i--) {
r = r * 10 + a.d[i]; // 被除数
if(r < b) {
c.d[i] = 0; // 不够除
} else {
c.d[i] = r / b; // 商
r = r % b; // 新余数
}
}
// 去除高位多余的0
while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
c.len--;
}
return c;
}void print(bign a) {
for(int i = a.len - 1; i >= 0; i--) {
printf("%d", a.d[i]);
}
}![[Pasted image 20251109182820.png]]
// 非递归版本
int cal(int n, int p) {
int ans = 0;
while (n) {
ans += n / p;
n /= p;
}
return ans;
}
// 递归版本
int cal(int n, int p) {
if (n < p) return 0;
return n / p + cal(n / p, p);
}- 应用：例如计算 n! 末尾零的个数（即质因子 5 的个数）。
组合数![[Pasted image 20251109182854.png]]直接计算阶乘容易溢出，因此有多种方法。
- 做法：分别计算 n!、m! 和 (n-m)!，然后相除。
- 缺点：阶乘增长快，仅适用于小数据（n ≤ 20）。
- 代码：
long long C(long long n, long long m) { long long ans = 1; for (long long i = 1; i <= n; i++) ans *= i; for (long long i = 1; i <= m; i++) ans /= i; for (long long i = 1; i <= n - m; i++) ans /= i; return ans; }
- 公式：( C(n, m) = C(n-1, m) + C(n-1, m-1) )，边界 ( C(n, 0) = C(n, n) = 1 )。
- 优点：避免阶乘计算，支持较大 n。
- 代码（带记忆化）：
long long res[67][67] = {0}; long long C(long long n, long long m) { if (m == 0 || m == n) return 1; if (res[n][m] != 0) return res[n][m]; return res[n][m] = C(n-1, m) + C(n-1, m-1); }
- 递推代码（计算整个表，时间复杂度 (O(n^2))）：
const int n = 60; long long res[n+1][n+1] = {0}; void calC() { for (int i = 0; i <= n; i++) { res[i][0] = res[i][i] = 1; for (int j = 1; j <= i/2; j++) { res[i][j] = res[i-1][j] + res[i-1][j-1]; res[i][i-j] = res[i][j]; // 利用对称性 } } }
- 做法：将 ( C(n, m) ) 写为 ( \frac{(n-m+1) \times (n-m+2) \times \cdots \times n}{1 \times 2 \times \cdots \times m} )，边乘边除。
- 优点：减少溢出风险，时间复杂度 (O(m))。
- 代码：
long long C(long long n, long long m) { long long ans = 1; for (long long i = 1; i <= m; i++) { ans = ans * (n - m + i) / i; // 先乘后除 } return ans; }
- 注意：在 n=62, m=31 时可能溢出，但比方法一支持的范围大。
当组合数很大时，常需计算模 p 的结果。p 可能是素数或非素数，需不同方法。
- 做法：递推过程中取模。
- 适用：n, m 较小（如 n ≤ 1000），p 任意。
- 代码：
int res[1010][1010] = {0}; int C(int n, int m, int p) { if (m == 0 || m == n) return 1; if (res[n][m] != 0) return res[n][m]; return res[n][m] = (C(n-1, m, p) + C(n-1, m-1, p)) % p; }
- 做法：
- 分解 n!、m!、(n-m)! 中质因子 p 的个数。
- 计算 ( C(n, m) ) 中 p 的个数 c。
- 用快速幂计算 ( p^c \mod p )（实际上 c 可能为 0，但这里是对每个质因子单独处理）。
- 适用：n 较大（如 n ≤ 10^6），p 任意。
- 代码：
// 假设 prime[] 为素数表 int C(int n, int m, int p) { int ans = 1; for (int i = 0; prime[i] <= n; i++) { int c = cal(n, prime[i]) - cal(m, prime[i]) - cal(n-m, prime[i]); ans = (ans * binaryPow(prime[i], c, p)) % p; } return ans; }
- 情况 1：m < p。直接计算，用逆元处理除法。
- 情况 2：m 可能 ≥ p。统计分子和分母中质因子 p 的个数，去除 p 后计算。
- 代码（情况 2）：
int C(int n, int m, int p) { int ans = 1, numP = 0; for (int i = 1; i <= m; i++) { int temp = n - m + i; while (temp % p == 0) { numP++; temp /= p; } ans = (ans * temp) % p; temp = i; while (temp % p == 0) { numP--; temp /= p; } ans = (ans * inverse(temp, p)) % p; // inverse 为逆元 } if (numP > 0) return 0; // 分子中 p 更多，结果为 0 else return ans; }
- 适用：m 较小（如 m ≤ 10^6），p 是素数。
- 定理：( C(n, m) \mod p = C(n \mod p, m \mod p) \times C(\lfloor n/p \rfloor, \lfloor m/p \rfloor) \mod p )。
- 优点：处理 n, m 很大但 p 较小的场景。
- 代码：
其中
int Lucas(int n, int m, int p) { if (m == 0) return 1; return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p; }
C(n % p, m % p, p)可用方法三的情况 1 计算。 - 适用：p 较小（如 p ≤ 10^6），n 和 m 很大。
- 做法：
- 将 p 分解为质因子幂积：( p = p_1^{k_1} p_2^{k_2} \cdots )。
- 对每个 ( p_i^{k_i} )，计算 ( C(n, m) \mod p_i^{k_i} )（用方法三的变形）。
- 用中国剩余定理（CRT）合并结果。
- 例子：计算 ( C(10, 3) \mod 24 )（24=2^3×3）。
- 分别计算 mod 8 和 mod 3，然后合并。
| 场景 | n, m 范围 | p 条件 | 推荐方法 |
|---|---|---|---|
| 小数据 | n, m ≤ 20 | 任意 | 直接计算（方法一） |
| 中小数据 | n, m ≤ 1000 | 任意 | 递推公式（方法一） |
| n 大、m 小 | m ≤ 10^6 | 任意 | 质因子分解（方法二） |
| n、m 大 | n, m 大 | p 小且为素数 | Lucas 定理（方法四） |
| p 非素数 | n, m 任意 | p 非素数 | 质因子分解 + CRT |