exCRT 萌新讲解

考虑没有 $m_i$ 互质的限制的同余方程

$\left\{ \begin{array} { l } { x \equiv a _ { 1 } \quad \left( \bmod m _ { 1 } \right) } \\ { x \equiv a _ { 2 } \quad \left( \bmod m _ { 2 } \right) } \\ { \vdots } \\ { x \equiv a _ { n } \quad \left( \bmod m _ { n } \right) } \end{array} \right.$

显然像 $\text{CRT}$ 那样处理是不行的 =w=，我们考虑一个子问题

$\left\{ \begin{array} { l } { x \equiv a _ { 1 } \quad \left( \bmod m _ { 1 } \right) } \\ { x \equiv a _ { 2 } \quad \left( \bmod m _ { 2 } \right) } \end{array} \right.$

把这个式子拆开，得

$\begin{array} { l } { x = a_1 + m_1 \times k_1 } \\ { x = a_2 + m_2 \times k_2} \end{array} \;\; (k_1,k_2\in \text{Z})$

也就是

$\begin{array} { a } { a_1 + m_1 \times k_1 = x = a_2 + m_2 \times k_2 } \\ { \Rightarrow m_2\times k_2 - m_1 \times k_1 = a_1 - a_2 } \end{array}$

令 $c = a_1 - a_2 , g = \gcd(m_1,m_2)$ , 考虑方程

$k _ { 2 } \times m _ { 2 } + k _ { 1 } \times m _ { 1 } = g$

使用 $\text{exgcd}$ 求解这个不定方程得到关于 $k_1$ 的一个解 $k'$

如果 $c$ 不事 $g$ 的倍数，那就自闭无解

若 $c$ 事 $g$ 的倍数，那么我们将上面的方程都乘上 $c\over g$ ，就能快乐得到方程 $k _ { 2 } \times m _ { 2 } - k _ { 1 } \times m _ { 1 } = c$ 的解

此时 $k'$ 就是原来求出的 $k'$ 的 $c\over g$ 倍，然后根据这个就可以推一下 $x$

这部分的代码很好写，伪代码:

g = exgcd(m1, m2, k1, k2); // 求出在 k2 * m2 - k1 * m1 = g 中 k1 的解和 gcd(m1, m2)
if ((a1 - a2) % g) return -1; // 判断无解的情况 =w=
k1 = (a1 - a2) / g * k1 % m2; // 求 k2 * m2 - k1 * m1 = c 中 k1 的解 k'

下一步就是求出 $x$ ，也就是这个子问题的一个特解 $x_0$ ，如果知道了 $x_0$ ，就可以得到 $x$ 的通解 $x = x_0 + t\times \text {lcm} (m_1,m_2),t\in \text{Z}$

特解显然十分好求，也就是对于方程 $x = a_1 + m_1 \times k_1$ ，我们求出了 $k_1$ 的解，就可以直接回代方程

这里有一点需要注意的是，对于 $k_1$ ，我们求出来的是 $-k_0$ 也就得到了 $x_0 = -k_1\times m_1+a_1$

我们转化成不定方程 $x \equiv x_0 \quad \left( \bmod \text { lcm} (m_1,m_2)\right)$

满足这个方程的解也必定满足上面两个方程，满足上面两个方程的解也一定满足这个方程，也就是说这个同余方程等价于刚刚的方程组

这样就完成了合并操作

代码也十分好写，就是

a1 -= m1 * k1; // 求出新的余数
m1 = m1 / g * m2; // 模数 lcm(m1, m2) = m1 * m2 / gcd(m1, m2)
a1 %= m1; // 当心爆 long long

我们可以不断合并来求出整个方程组的通解，也就是把上面过程执行 $n-1$ 次

代码很好写，这里就不放了 = =

By Shq

exCRT 讲解

exCRT 萌新讲解