中国剩余定理 - NOI提高级教程

📖 中国剩余定理：“韩信点兵”的数学模型

中国剩余定理 (CRT) 是数论中的一个经典定理，用于求解一元线性同余方程组。其在中国古代数学名著《孙子算经》中便有记载，被称为“物不知数”或“韩信点兵”问题。

📐 孙子算经原题与方程组模型

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”对应的同余方程组为：

$\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases}$

📐 构造性解法推导

设模数两两互质，设 $M = \prod_{i=1}^k m_i$。对于每一个方程 $i$，令辅助大模数 $M_i = M / m_i$：

求出 $M_i$ 模 $m_i$ 的逆元 $t_i$，即满足 $M_i t_i \equiv 1 \pmod{m_i}$。
构造特解项 $w_i = M_i t_i$。这一项有一个神奇性质：它模 $m_i$ 为 $1$，而模所有其他模数 $m_j \; (j \neq i)$ 均为 $0$！
方程组在模 $M$ 意义下的唯一解为：
$x \equiv \sum_{i=1}^k a_i M_i t_i \pmod M$

x ≡ mod

输入方程组的余数和模数（模数必须两两互质），点击“刻度尺扫描”查看同余刻度碰撞对齐过程。

模数乘积 M 105

互质校验是

构造算式和 233

最小正整数解 x 23

📏 同余余数尺对齐探针 (Modular Ruler Matching Panel)

数学构造解析：$M = 105$

// 扩欧计算模逆元
long long extGcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long d = extGcd(b, a % b, x1, y1);
    x = y1; y = x1 - (a / b) * y1;
    return d;
}
long long inv(long long a, long long m) {
    long long x, y; extGcd(a, m, x, y); return (x % m + m) % m;
}
// CRT 核心求解
long long CRT(int k, long long a[], long long m[]) {
    long long M = 1, ans = 0;
    for (int i = 0; i < k; i++) M *= m[i];
    for (int i = 0; i < k; i++) {
        long long Mi = M / m[i];
        long long ti = inv(Mi, m[i]);
        ans = (ans + a[i] * Mi % M * ti % M) % M;
    }
    return ans;
}

📋 尺标扫描分析日志