数论之中国剩余定理：从孙子算经到算法竞赛实现
一、问题溯源：从'物不知其数'到线性同余方程组
1.1 经典问题引入
《孙子算经》中有云：'今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？'翻译成数学语言，就是求解以下线性同余方程组： （此处为公式图示） 这个问题的最小正整数解是 23，而中国剩余定理正是为解决这类'多模数同余'问题而生。
1.2 线性同余方程组的定义
一般地，线性同余方程组的标准形式为： （此处为公式图示） 其中 m1, m2, ..., mn 是模数，r1, r2, ..., rn 是余数，我们的目标是找到满足所有方程的最小非负整数解 x。
1.3 CRT 的核心前提
中国剩余定理的适用条件是：所有模数 m1, m2, ..., mn 两两互质。这一前提是 CRT 构造解的基础，后续我们会看到，正是因为模数互质，才能保证逆元存在，从而顺利构造出满足所有方程的解。
二、CRT 的原理：构造法的精妙之处
CRT 的核心思想是'分而治之、逐步构造'——先为每个方程构造一个局部解，使得该解仅满足当前方程，而对其他方程的余数为 0；再将所有局部解相加，得到满足所有方程的全局解。
2.1 构造步骤拆解
设方程组有 n 个方程，模数两两互质，定义： （此处为公式图示） 则方程组的一个解为： （此处为公式图示）
2.2 构造逻辑验证
为什么这样的构造能满足所有方程？以第 i 个方程为例： 叠加后， （此处为公式图示） 恰好满足第 i 个方程。 对于 j=i， （此处为公式图示） 因此 （此处为公式图示） ； 对于 j≠i，Mj 包含 mi 这个因子（因为 M = m1 * ... * mn，而 mi 是 M 的因子且 mi 与 mj 互质），因此 （此处为公式图示） ；
三、核心工具：逆元与快速乘的实现
要实现 CRT，必须解决两个关键问题：乘法逆元求解和大整数溢出防护。
3.1 乘法逆元求解（扩展欧几里得算法）
由于 CRT 中模数两两互质，Mi 与 mi 互质，逆元一定存在。我们用扩展欧几里得算法求解逆元，该方法适用于任意互质的模数对，通用性强。
扩展欧几里得算法原理
扩展欧几里得算法不仅能计算 a 和 b 的最大公约数，还能找到整数 x 和 y，使得 ax+by=gcd(a,b)。当 a 与 b 互质时，gcd(a,b)=1，此时 x 就是 a 模 b 的逆元。
C++ 实现扩展欧几里得算法
#include <iostream>
using namespace std;
typedef long long LL;
// 扩展欧几里得算法：返回 gcd(a,b)，通过引用返回 ax + by = gcd(a,b) 的特解 x,y
LL exgcd(LL a, LL b, LL& x, LL& y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
LL x1, y1, d = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - a / b * y1;
d;
}
{
LL x, y;
(a, m, x, y);
(x % m + m) % m;
}
{
LL a = , m = ;
cout << a << << m << << (a, m) << endl;
;
}