当前位置：首页 > news >正文

扩展中国剩余定理 ExCRT 总结

news 2026/3/27 0:07:48

求解类似于下图的问题

求法数学归纳法实现 ExCRT

设前 \(k - 1\) 个方程的最小非负整数解为 \(x_0\)，前 \(k - 1\) 个方程的模数的 \(\operatorname{lcm}\) 为 \(M\)，则其通解为 \(X = x_0 + Mt\)。

对于第 \(k\) 个方程

\[x \equiv a_k \pmod {m_k} \]

则我们要找到一些 \(t\) 使得满足下式，这样才能同时满足前 \(k\) 个方程（其实就是找一个满足下式的解的子集）

\[X \equiv a_k \pmod {m_k} \]

\[x_0 + Mt \equiv a_k \pmod {m_k} \]

\[Mt \equiv a_k - x_0 \pmod {m_k} \]

转化为不定方程

\[Mt + m_ks = a_k - x_0 \]

用 Exgcd 解出 \(t\) 的解集，就能求出同时满足前 \(k\) 个方程的解集。
若方程无解，则方程组无解。
否则更新答案 \(x_0 = x_0 + Mt,M = \operatorname{lcm}(M, m_k)\)。

Code

#define int long long
int ExCRT(int a[], int m[]) {int ans = 0, lcm = 1;for (int i = 1; i <= n; i++) {int x = 0, y = 0, c = ((a[i] - ans) % m[i] + m[i]) % m[i];;int d = Exgcd(lcm, m[i], x, y);if (c % d) {	return -1;}int mod = lcm / d * m[i];x = F(Mul(x, c / d, mod), mod);ans = ans + Mul(x, lcm, mod);lcm = mod;}return ans;
}

要点

#define int long long 在数学题中尽量用
注意乘法是否超出 long long 范围
注意要把 ans 变成非负整数，或把 x 变成非负整数
初始将 int ans = 0, lcm = 1
事实上，\(x\) 的模数是 \(\frac{m[i]}{d}\) 还是 \(mod\) 都是一样的，因为 \(\frac{m[i]}{d} \mid mod\) 且最终反正都是会模上 \(mod\)

Problem

P4777 【模板】扩展中国剩余定理（EXCRT）

P3868 [TJOI2009] 猜数字

题解

\[b_i \mid (n - a_i) \]

\[n - a_i \equiv 0 \pmod {b_i} \]

\[n \equiv a_i \pmod {b_i} \]

板子即可

P2421 [NOI2002] 荒岛野人

题解

因为答案值域比较小，所以考虑枚举答案 \(m\)，那么我们需要判断一个答案是否合法，也就是要判断是否会出现两个奶龙在同一个洞里。因为 \(n\) 很小，所以枚举冲突的两只奶龙。两只奶龙 \(i, j\) 冲突等价于存在 \(t\) 使得

\[c_i + tp_i \equiv c_j + tp_j \pmod m (t \le l_i, l_j) \]

\[t(p_i - p_j) \equiv c_j - c_i \pmod m (t \le l_i, l_j) \]

这是一个同余方程的形式，但我们有很多个这样的同余方程，所以可以用 ExCRT 来求解。吗？
事实上，我们要求的是解的并集（是否有某个方程存在解，等价于方程解的并集是否为空），而 ExCRT 求解的是满足所有方程的解集，也就是解的交集。

所以这道题的意义出现在 ExCRT 专题的原因就是最后一句话。

启示

最后一句话

P4774 [NOI2018] 屠龙勇士

~~其实屠的是我这个奶龙吧~~

题解

读题可知，在屠龙过程中我们能决策的只有 \(x\)。我们可以用平衡树求出对每条龙会用那把剑打他，记剑的攻击力为 \(atk_i\)。则我们就是要找到最小 \(x\) 使得

\[a_i - atk_ix \equiv 0 \pmod {p_i}(a_i \le atk_ix) \]

可化为

\[atk_ix \equiv a_i \pmod {p_i}(a_i \le atk_ix) \]

这正是一个同余方程的形式，我们先考虑求出这些同余方程的解的交集，然后在满足后面的条件。

将原同余方程记作

\[a_ix \equiv b_i \pmod {m_i} \]

我们要求交集，所以要用 ExCRT，但这并不是标准的 \(x \equiv b_i \pmod {m_i}\) 的形式。并且 \(a_i\) 不一定与 \(m_i\) 互质，所以不一定有逆元可以把他移到右边。这时，我们考虑能否使用 ExCRT 的变种~~ExExCRT~~来求解形如上式的同余方程组的解的交集。

数学归纳法实现 ExExCRT

设前 \(k - 1\) 个方程的最小非负整数解为 \(x_0\)，则其通解为 \(X = x_0 + Mt\)。（这里不将 \(M\) 定义为 \(m_i(i < k)\) 的 \(\operatorname{lcm}\)。因为求解的过程中，\(M\) 的定义就是 \(x\) 的解系中的周期，在 ExCRT 中定义为 \(\operatorname{lcm}\) 是因为最小周期恰好就是这个，这样定义方便理解和计算。）
对于第 \(k\) 个方程

\[a_kx \equiv b_k \pmod {m_k} \]

则我们要找到一些 \(t\) 使得满足下式，这样才能同时满足前 \(k\) 个方程（其实就是找一个满足下式的解的子集）

\[a_kX \equiv b_k \pmod {m_k} \]

\[a_k(x_0 + Mt) \equiv b_k \pmod {m_k} \]

\[a_kMt \equiv b_k - a_kx_0 \pmod {m_k} \]

转化为不定方程

\[a_kMt + m_ks = b_k - a_kx_0 \]

在 Exgcd 求解过程中记作

\[At + Bs = C \]

用 Exgcd 求解。
若方程无解，则方程组无解。
否则更新答案 \(x_0 = x_0 + Mt,M = \frac{MB}{\gcd(A, B)} = \frac{Mm_k}{\gcd(a_kM, m_k)}\)。（在 ExCRT 中 \(M = \operatorname{lcm}(M, m_k)\)，这是基于 \(M\) 的特殊定义得出的。但在 ExExCRT 中，\(M\) 不存在这样的定义，所以要从解系的角度求解出 \(M\)。设，在前 \(k - 1\) 个方程中，\(x\) 的解系为 \(X = x_0 + Mt\)。在 Exgcd 中，我们可以得到 t 的解系 \(T = t_0 + \frac{uB}{\gcd(A, B)} = t_0 + \frac{um_k}{\gcd(a_kM, m_k)}\)，则可得 \(x\) 的新解系 \(X = x_0 + MT = x_0 + M(t_0 + \frac{um_k}{\gcd(a_kM, m_k)}) = (x0 + Mt_0) + \frac{Mum_k}{\gcd(a_kM, m_k)}\)。在解系的定义中，\(X = x_0 + Mt\) 中的 \(t\)，和 \(X = (x0 + Mt_0) + \frac{Mum_k}{\gcd(a_kM, m_k)}\) 中的 \(u\) 都只是周期的乘数，它们的定义域都是非负整数集，所以可以等效替换。得 \(X = (x0 + Mt_0) + \frac{Mm_k}{\gcd(a_kM, m_k)}t\)，从这个形式可以看出 \(M = \frac{Mm_k}{\gcd(a_kM, m_k)}\)。