「EXCRT」拓展中国剩余定理学习笔记

把之前屯的博客发一下(

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

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

1
2
3
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\pmod {\text{lcm} (m_1,m_2)}

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

这样就完成了合并操作

代码也十分好写,就是

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

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

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


感觉exCRT比CRT简单多了(

坚持原创技术分享,您的支持将鼓励我继续创作!