C++算法
数论之中国剩余定理：从孙子算经到算法竞赛实现
中国剩余定理用于求解模数两两互质的线性同余方程组。核心思想是构造法，通过局部解叠加得到全局解。实现需结合扩展欧几里得算法求逆元及快速乘防止溢出。本文详解原理、C++ 代码实现及经典例题，涵盖常见误区与避坑指南。
中国剩余定理用于求解模数两两互质的线性同余方程组。核心思想是构造法，通过局部解叠加得到全局解。实现需结合扩展欧几里得算法求逆元及快速乘防止溢出。本文详解原理、C++ 代码实现及经典例题，涵盖常见误区与避坑指南。
《孙子算经》中有云：'今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？'翻译成数学语言，就是求解以下线性同余方程组： （此处为公式图示） 这个问题的最小正整数解是 23，而中国剩余定理正是为解决这类'多模数同余'问题而生。
一般地，线性同余方程组的标准形式为： （此处为公式图示） 其中 m1, m2, ..., mn 是模数，r1, r2, ..., rn 是余数，我们的目标是找到满足所有方程的最小非负整数解 x。
中国剩余定理的适用条件是：所有模数 m1, m2, ..., mn 两两互质。这一前提是 CRT 构造解的基础，后续我们会看到，正是因为模数互质，才能保证逆元存在，从而顺利构造出满足所有方程的解。
CRT 的核心思想是'分而治之、逐步构造'——先为每个方程构造一个局部解，使得该解仅满足当前方程，而对其他方程的余数为 0；再将所有局部解相加，得到满足所有方程的全局解。
设方程组有 n 个方程，模数两两互质，定义： （此处为公式图示） 则方程组的一个解为： （此处为公式图示）
为什么这样的构造能满足所有方程？以第 i 个方程为例： 叠加后， （此处为公式图示） 恰好满足第 i 个方程。 对于 j=i， （此处为公式图示） 因此 （此处为公式图示） ； 对于 j≠i，Mj 包含 mi 这个因子（因为 M = m1 * ... * mn，而 mi 是 M 的因子且 mi 与 mj 互质），因此 （此处为公式图示） ；
要实现 CRT，必须解决两个关键问题：乘法逆元求解和大整数溢出防护。
由于 CRT 中模数两两互质，Mi 与 mi 互质，逆元一定存在。我们用扩展欧几里得算法求解逆元，该方法适用于任意互质的模数对，通用性强。
扩展欧几里得算法不仅能计算 a 和 b 的最大公约数，还能找到整数 x 和 y，使得 ax+by=gcd(a,b)。当 a 与 b 互质时，gcd(a,b)=1，此时 x 就是 a 模 b 的逆元。
#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;
return d;
}
// 求 a 模 m 的逆元（a 与 m 互质）
LL get_inv(LL a, LL m) {
LL x, y;
exgcd(a, m, x, y);
// 转为最小正整数逆元
return (x % m + m) % m;
}
int main() {
LL a = 35, m = 3;
cout << a << "模" << m << "的逆元为：" << get_inv(a, m) << endl; // 输出 2
return 0;
}
当模数较大时（如 1e5×1e5×1e5=1e15），直接乘法会超出 long long 范围导致溢出。快速乘（又称龟速乘）通过将乘法转化为加法，结合模运算，避免溢出。
快速乘的核心是二进制分解：将 a×b 分解为 a×2^0+a×2^1+...+a×2^k，每次累加后取模，确保中间结果不溢出。
// 快速乘：计算 (a*b) mod p，避免溢出
LL qmul(LL a, LL b, LL p) {
LL ret = 0;
while (b) {
if (b & 1) {
ret = (ret + a) % p;
}
a = (a + a) % p;
b >>= 1;
}
return ret;
}
int main() {
LL a = 1e18, b = 1e18, p = 1e9 + 7;
cout << qmul(a % p, b % p, p) << endl; // 输出 (a*b) mod p 的结果
return 0;
}
结合逆元求解和快速乘，我们可以写出 CRT 的通用实现，适用于所有模数两两互质的线性同余方程组。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 15;
LL r[N], m[N]; // r[i] 为余数，m[i] 为模数
int n; // 方程个数
// 扩展欧几里得算法
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;
return d;
}
// 快速乘
LL qmul(LL a, LL b, LL p) {
LL ret = 0;
while (b) {
if (b & 1) ret = (ret + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ret;
}
// 中国剩余定理：返回最小非负解，无解返回 -1（模数互质时一定有解）
LL crt() {
LL M = 1;
for (int i = 0; i < n; ++i) {
M *= m[i]; // 全局模数
}
LL ret = 0;
for (int i = 0; i < n; ++i) {
LL Mi = M / m[i];
LL inv_Mi, _;
// 求 Mi 模 m[i] 的逆元
exgcd(Mi, m[i], inv_Mi, _);
inv_Mi = (inv_Mi % m[i] + m[i]) % m[i];
// 累加局部解：r[i] * Mi * inv_Mi，用快速乘避免溢出
ret = (ret + qmul(qmul(r[i], Mi, M), inv_Mi, M)) % M;
}
// 确保返回最小非负解
return (ret % M + M) % M;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 输入方程个数
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> m[i] >> r[i];
}
LL ans = crt();
cout << "最小非负解：" << ans << endl;
return 0;
}
qmul 确保大整数乘法不溢出，支持模数乘积达 1e18 级别。题目描述：曹冲养猪，建 ai 个猪圈剩 bi 头猪（ai 两两互质），求最少养猪数量。 输入描述：第一行 n，接下来 n 行每行两个整数 ai、bi（ai 为模数，bi 为余数）。 输出描述：最小正整数解。 示例输入： 3 3 1 5 1 7 2 示例输出：16。
直接套用 CRT 模板，将 ai 作为模数 mi，bi 作为余数 ri，调用 CRT 函数即可。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 15;
LL r[N], m[N];
int n;
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; return d;
}
LL qmul(LL a, LL b, LL p) {
LL ret = 0; while (b) { if (b & 1) ret = (ret + a) % p; a = (a + a) % p; b >>= 1; } return ret;
}
LL crt() {
LL M = 1; for (int i = 0; i < n; ++i) M *= m[i];
LL ret = 0;
for (int i = 0; i < n; ++i) {
LL Mi = M / m[i];
LL inv_Mi, y;
exgcd(Mi, m[i], inv_Mi, y);
inv_Mi = (inv_Mi % m[i] + m[i]) % m[i];
ret = (ret + qmul(qmul(r[i], Mi, M), inv_Mi, M)) % M;
}
return (ret + M) % M;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; ++i) { cin >> m[i] >> r[i]; }
cout << crt() << endl;
return 0;
}
示例输入中，模数 m=[3,5,7]，余数 r=[1,1,2]： 全局模数 M=105；局部解分别为：1×35×2=70，1×21×1=21，2×15×1=30；总和 70+21+30=121，121 mod 105=16，与示例输出一致。
题目描述：给定两组数字 a1...ak 和 b1...bk（bi 两两互质），求最小的 n 使得 bi|(n−ai)（即 n≡ai(modbi)）。 输入描述：第一行 k，第二行 a1...ak，第三行 b1...bk。 输出描述：最小正整数 n。 示例输入： 3 1 2 3 2 3 5 示例输出：23。
方程转化：n≡ai(mod bi)，直接对应 CRT 的标准形式；注意点：ai 可能为负数，需先将余数调整为非负（ri=(ai%bi+bi)%bi）。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 15;
LL r[N], m[N];
int n;
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; return d;
}
LL qmul(LL a, LL b, LL p) {
LL ret = 0; while (b) { if (b & 1) ret = (ret + a) % p; a = (a + a) % p; b >>= 1; } return ret;
}
LL crt() {
LL M = 1; for (int i = 0; i < n; ++i) M *= m[i];
LL ret = 0;
for (int i = 0; i < n; ++i) {
LL Mi = M / m[i];
LL inv_Mi, y;
exgcd(Mi, m[i], inv_Mi, y);
inv_Mi = (inv_Mi % m[i] + m[i]) % m[i];
// 累加时确保余数非负
ret = (ret + qmul(qmul((r[i] % m[i] + m[i]) % m[i], Mi, M), inv_Mi, M)) % M;
}
return (ret + M) % M;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; ++i) { cin >> r[i]; }
for (int i = 0; i < n; ++i) { cin >> m[i]; }
cout << crt() << endl;
return 0;
}
a * b % p 计算，当 a 和 b 均为 1e9 时溢出；qmul 替代直接乘法，确保中间结果不溢出。long long 范围；中国剩余定理是解决线性同余方程组的经典算法，其核心是'构造法'，通过局部解叠加得到全局解。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online