中国剩余定理（CRT）

从分糖果到中国剩余定理：一次搞定多个余数条件

想象一个场景：你有一袋糖果，想知道最少有多少颗。你发现：

• 如果按 3 人一组分，还剩 2 颗；
• 如果按 5 人一组分，还剩 3 颗；
• 如果按 7 人一组分，还剩 2 颗。

那糖果总数是多少？这其实就是一个同余问题：我们要找一个数 $x$，同时满足三个“除以某数余某数”的条件。中国剩余定理（Chinese Remainder Theorem，简称 CRT）就是专门用来求解这类问题的数学工具。它告诉我们：当每个除数之间两两互质（没有公共的因数）时，一定存在一个唯一的答案，并且这个答案在 0 到除数乘积之间。

本文会用通俗的语言、生活中的例子和 C++ 代码，带你彻底掌握这个方法。即使你之前没有接触过同余，也能跟着步骤学会。

1. 什么是“同余”？先看几个生活例子

“同余”听起来很数学，但生活中处处有它：

• 钟表时间：现在是上午 10 点，再过 5 小时是下午 3 点（15 点）。实际上，10 + 5 = 15，但 15 点相当于下午 3 点，也就是 15 ≡ 3 (mod 12) —— 除以 12 的余数相同。
• 星期几：今天是星期一，过 7 天后还是星期一，过 14 天后还是星期一……这是模 7 的同余。
• 分糖果：糖果数除以 3 余 2，可以写成 $x \equiv 2 \pmod{3}$。意思是：$x$ 除以 3 的余数是 2。

所以，“同余”就是“余数相同”的意思。中国剩余定理解决的问题是：同时满足多个这样的余数条件，求最小的正整数解。

2. 暴力枚举法——最直接的方法

对于小数字，我们可以用循环一个个试。从 0 开始，每次检查当前数是否满足所有余数条件，直到找到为止。不用担心数字太大，因为答案一定在 0 到所有除数的乘积之间。为什么？因为如果超过乘积，减掉乘积后余数不变，所以最小解肯定在 [0, 乘积) 范围内。

下面就是原来的 C++ 代码，我保留了它并补充了中文注释：

#include <iostream>
using namespace std;

int main() {
    // 给定的余数和除数
    int remainder[3] = {2, 3, 2};   // 余数：除以3余2，除以5余3，除以7余2
    int modulus[3]  = {3, 5, 7};   // 除数（模数）：3, 5, 7

    // 最大可能范围：除数乘积 3*5*7 = 105
    int limit = modulus[0] * modulus[1] * modulus[2];
    int x;  // 用来存储尝试的数

    // 从0开始试到limit-1，因为答案可能在0~104之间
    for (x = 0; x < limit; x++) {
        bool found = true;                 // 假设当前x满足所有条件
        for (int i = 0; i < 3; i++) {      // 遍历每个除数
            if (x % modulus[i] != remainder[i]) {  // 如果不满足某一个余数条件
                found = false;             // 标记为不满足
                break;                     // 跳出内层循环，继续试下一个x
            }
        }
        if (found) {                       // 如果所有条件都满足
            cout << "最少有 " << x << " 颗糖果" << endl;
            return 0;                      // 找到答案，程序结束
        }
    }
    // 如果循环结束还没找到，说明无解（但互质情况下不会发生）
    cout << "无解" << endl;
    return 0;
}

运行输出：最少有 23 颗糖果。验证一下：23 ÷ 3 = 7 余 2，23 ÷ 5 = 4 余 3，23 ÷ 7 = 3 余 2，完全正确！

注意：当除数很多或数值很大时，暴力枚举会非常慢。例如除数分别是 23、29、31，乘积接近 2 万，循环次数不多，但如果除数是 100、101、103，乘积超过 100 万，循环就有点慢。更大时，我们需要更高效的方法。

3. 高效解法——逐个合并（真正的中国剩余定理）

暴力枚举虽然简单，但不够“聪明”。中国剩余定理的真正威力在于可以用数学方法直接算出答案，即使除数非常大也能快速求解。核心思想是 “逐个合并”：先把前两个条件合并成一个等效的条件，再与第三个合并，以此类推。

举个例子，先合并前两个条件：

• 条件1：$x \equiv 2 \pmod{3}$
• 条件2：$x \equiv 3 \pmod{5}$

我们要找一个数，它同时满足这两个条件。可以写成 $x = 3k + 2$，代入第二个条件：$3k + 2 \equiv 3 \pmod{5}$，即 $3k \equiv 1 \pmod{5}$。问题变成解这个线性同余方程：$3k \equiv 1 \pmod{5}$。这需要求 3 在模 5 下的乘法逆元。因为 $3 \times 2 = 6 \equiv 1 \pmod{5}$，所以 3 的逆元是 2。两边乘以 2 得 $k \equiv 2 \pmod{5}$，即 $k = 5m + 2$。代入 $x$ 得 $x = 3(5m+2) + 2 = 15m + 8$。所以前两个条件合并成了一个新条件：$x \equiv 8 \pmod{15}$。

再与第三个条件 $x \equiv 2 \pmod{7}$ 合并：

• $x = 15m + 8$，代入第三个条件：$15m + 8 \equiv 2 \pmod{7}$，即 $15m \equiv -6 \pmod{7}$。计算 $15 \mod 7 = 1$，$-6 \mod 7 = 1$，所以 $m \equiv 1 \pmod{7}$，即 $m = 7n + 1$。代入得 $x = 15(7n+1) + 8 = 105n + 23$。最小正整数解就是 23（当 n=0）。

这个过程中，关键步骤是求乘法逆元。当模数较大时，可以用扩展欧几里得算法高效求逆元。下面给出一个用函数实现的通用 CRT 求解代码，可以处理任意数量的两两互质的除数。

#include <iostream>
using namespace std;

// 扩展欧几里得算法：返回 gcd(a,b)，并求 ax + by = gcd 的一组解 (x, y)
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

// 求 a 在模 m 下的乘法逆元（要求 a 和 m 互质）
long long mod_inverse(long long a, long long m) {
    long long x, y;
    exgcd(a, m, x, y);
    // 确保逆元为正数
    return (x % m + m) % m;
}

// 中国剩余定理求解：传入余数数组 r 和模数数组 m，数组长度为 n，返回 x
// 要求所有模数两两互质
long long crt(long long r[], long long m[], int n) {
    long long M = 1;                 // 所有模数的乘积
    for (int i = 0; i < n; i++) {
        M *= m[i];
    }
    long long result = 0;            // 累加结果
    for (int i = 0; i < n; i++) {
        long long Mi = M / m[i];     // 除了第 i 个模数外的乘积
        long long inv = mod_inverse(Mi % m[i], m[i]);  // Mi 在模 m[i] 下的逆元
        result = (result + r[i] * Mi % M * inv % M) % M;
    }
    return result;
}

int main() {
    // 分糖果的例子：余数 {2,3,2}，模数 {3,5,7}
    long long remainder[] = {2, 3, 2};
    long long modulus[]   = {3, 5, 7};
    int n = 3;

    long long answer = crt(remainder, modulus, n);
    cout << "最少有 " << answer << " 颗糖果" << endl;  // 输出 23
    return 0;
}

这个程序用到了扩展欧几里得算法，可能对初学者有点复杂，但它是处理大数字时的高效方法。你可以先理解暴力枚举的思想，再慢慢学习这个“高级版”。

4. 常见错误与注意事项

• 除数不互质：如果除数之间有公因数（例如 4 和 6 不互质），中国剩余定理不能直接应用。此时可能无解，或者有多个解。实际应用时要先化简或者用更通用的方法（如合并模数时使用最小公倍数）。
• 余数范围：余数必须小于除数，否则条件本身矛盾（例如 $x \equiv 5 \pmod{3}$ 无意义，因为除以 3 的余数只能是 0,1,2）。
• 暴力枚举的起始点：一般从 0 开始试，但有时答案要求正整数，可以改成从 1 开始。注意：如果答案可能为 0（例如所有余数都是 0），则 0 是一个解，程序会输出 0。
• 溢出：当除数乘积很大时（比如超过 2^63），代码中的 long long 可能不够。C++ 中可以用 __int128 或大数库，但通常 CSP-S 题目不会超出 64 位。

5. 完整示例：零花钱问题

小红的零花钱按周发放。她发现：

• 如果每次发 9 元，最后会多出 4 元；
• 如果每次发 11 元，最后会多出 7 元；
• 如果每次发 13 元，最后会多出 10 元。

她至少有多少零花钱？用 CRT 求解：

#include <iostream>
using namespace std;

// 同上，扩展欧几里得和 CRT 函数略（可复制前面代码）
// ...

int main() {
    long long remainder[] = {4, 7, 10};   // 余数
    long long modulus[]   = {9, 11, 13};  // 模数（两两互质）
    int n = 3;

    long long answer = crt(remainder, modulus, n);
    cout << "最少有 " << answer << " 元" << endl;
    // 预期结果：9*11*13=1287，手工计算稍繁琐，程序直接输出
    return 0;
}

你可以用暴力枚举先验证一下（比如循环到 1286），看结果是否一致。这样既能理解原理，也能体会到高效方法的威力。

6. 相关指引

掌握了中国剩余定理，你还可以继续学习：

• 扩欧与逆元：这是 CRT 高效实现的基础，也是数论里非常实用的工具。
• 孙子定理：中国剩余定理的另一个名字，来源于中国古代《孙子算经》中的“物不知数”问题。
• 非互质情况的合并：当模数不互质时，可以用“逐步合并法”求解，但需要处理无解的情形。
• 模线性方程组：CRT 是这类问题的标准解法，也是密码学（如 RSA）的基础之一。

如果你对暴力枚举已经得心应手，不妨动手写一个程序，让用户输入任意多个余数和除数，然后输出答案——无论是暴力还是高效算法，都能加深理解。尝试用不同数字测试，你会发现数学规律真的很神奇！