数论之中国剩余定理：从孙子算经到算法竞赛实现

3.2 快速乘：大整数溢出防护

当模数较大时（如 1e5×1e5×1e5=1e15），直接乘法会超出 long long 范围导致溢出。快速乘（又称龟速乘）通过将乘法转化为加法，结合模运算，避免溢出。

快速乘原理

快速乘的核心是二进制分解：将 a×b 分解为 a×2^0+a×2^1+...+a×2^k，每次累加后取模，确保中间结果不溢出。

C++ 实现快速乘

// 快速乘：计算 (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 的完整 C++ 实现

结合逆元求解和快速乘，我们可以写出 CRT 的通用实现，适用于所有模数两两互质的线性同余方程组。

4.1 实现代码

#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;
}

4.2 代码分析

• 时间复杂度：O(nlogm)，其中 n 是方程个数，logm 是扩展欧几里得算法和快速乘的时间复杂度；
• 空间复杂度：O(n)，仅需存储模数和余数数组；
• 适用性：适用于所有模数两两互质的线性同余方程组，返回最小非负解；
• 溢出防护：通过快速乘 qmul 确保大整数乘法不溢出，支持模数乘积达 1e18 级别。

五、实战例题 1：洛谷 P1495【模板】中国剩余定理 / 曹冲养猪

5.1 题目分析

题目描述：曹冲养猪，建 ai 个猪圈剩 bi 头猪（ai 两两互质），求最少养猪数量。 输入描述：第一行 n，接下来 n 行每行两个整数 ai、bi（ai 为模数，bi 为余数）。 输出描述：最小正整数解。 示例输入： 3 3 1 5 1 7 2 示例输出：16。

5.2 解题思路

直接套用 CRT 模板，将 ai 作为模数 mi，bi 作为余数 ri，调用 CRT 函数即可。

5.3 C++ 实现

#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;
}

5.4 代码验证

示例输入中，模数 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，与示例输出一致。

六、实战例题 2：洛谷 P3868 [TJOI2009] 猜数字

6.1 题目分析

题目描述：给定两组数字 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。

6.2 解题思路

方程转化：n≡ai(mod bi)，直接对应 CRT 的标准形式；注意点：ai 可能为负数，需先将余数调整为非负（ri=(ai%bi+bi)%bi）。

6.3 C++ 实现

#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;
}

七、常见误区与避坑指南

7.1 模数不互质直接套用 CRT

• 误区：忽略 CRT'模数两两互质'的前提，直接代入代码导致错误；
• 避坑：先检查所有模数对的最大公约数，若存在非 1 的情况，改用 EXCRT；
• 验证方法：对于模数 m1,m2,...,mn，需满足 gcd(mi,mj)=1（i≠j）。

7.2 大整数乘法溢出

• 误区：直接使用 a * b % p 计算，当 a 和 b 均为 1e9 时溢出；
• 避坑：统一使用快速乘 qmul 替代直接乘法，确保中间结果不溢出。

7.3 余数为负数未调整

• 误区：当 ri 为负数时（如 x≡−1(mod5)），直接代入计算；
• 避坑：将余数调整为非负：(ri % mi + mi) % mi。

7.4 逆元求解错误

• 误区：使用费马小定理求逆元但未确认模数为质数；
• 避坑：CRT 中模数不一定是质数，优先用扩展欧几里得算法求逆元（通用无限制）。

7.5 全局模数计算溢出

• 误区：当 n 较大（如 n=10，每个模数 1e5），M=1e5^10 远超 long long 范围；
• 避坑：此时需用 __int128 存储 M，或在快速乘中实时取模，避免全局模数溢出。

总结

中国剩余定理是解决线性同余方程组的经典算法，其核心是'构造法'，通过局部解叠加得到全局解。