CRT

CRT 是用来解决一元线性同余方程组的。

例如，对于下面的方程组：
$\begin{cases}x\equiv a_1\;(\,\mathrm {mod}\; m_1)\\ x\equiv a_2\;(\,\mathrm {mod}\; m_2)\\ \;\;\;\;\;\;\;\;\;\cdots\cdots \\ x\equiv a_n\;(\,\mathrm {mod}\; m_n) \end{cases}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​x≡a1​(modm1​)x≡a2​(modm2​)⋯⋯x≡an​(modmn​)​

其中，$m_1,m_2,...,m_n$m1​,m2​,...,mn​ 是两两互质的整数。

我们令 $m=\prod\limits_{i=1}^nm_i$m=i=1∏n​mi​，$M_i=\frac{m}{m_i}$Mi​=mi​m​，$t_i$ti​ 是方程 $M_it_i\equiv1(\,\mathrm {mod}\; m_1)$Mi​ti​≡1(modm1​) 的一个解。

那么 $x$x 有整数解，解为 $x=\sum\limits_{i=1}^na_iM_it_i$x=i=1∑n​ai​Mi​ti​。

证明如下：
因为 $M_i=\frac{m}{m_i}$Mi​=mi​m​ 是除了 $m_i$mi​ 之外所有模数的倍数，所以对于 $\forall k≠ i$∀k̸​=i，有 $M_i\equiv0(\,\mathrm {mod}\; m_k)$Mi​≡0(modmk​)，也即 $a_iM_it_i\equiv0(\,\mathrm {mod}\; m_k)$ai​Mi​ti​≡0(modmk​)。
又因为 $a_iM_it_i\equiv a_i(\,\mathrm {mod}\; m_i)$ai​Mi​ti​≡ai​(modmi​)，所以如果代入 $x=\sum\limits_{i=1}^na_iM_it_i$x=i=1∑n​ai​Mi​ti​，原方程组成立。
可以理解成每个 $a_iM_it_i$ai​Mi​ti​ 只对 $i$i 这个方程有贡献，对其他方程都没有影响。
证毕。

这时，解出来的 $x$x 是一个特解，通解可以用 $x+km(k\in \mathbb Z)$x+km(k∈Z) 表示。

如果题目要我们求最小整数解，只需把 $x$x 对 $m$m 取模，使得 $x\in[\;0\;,\;m-1\;]$x∈[0,m−1] 即可。

模板题：[51nod 1079] 中国剩余定理

exCRT

CRT 有一个缺陷，就是它只能解决 $m$m 两两互质问题，若不满足 $m$m 两两互质，我们就要用到 exCRT 算法了。

我们考虑能否把 $\begin{cases}x\equiv a_1\;(\,\mathrm {mod}\; m_1)\\ x\equiv a_2\;(\,\mathrm {mod}\; m_2) \end{cases}${x≡a1​(modm1​)x≡a2​(modm2​)​ 合并成一个方程。

把这个方程组变形，得到 $\begin{cases}x=a_1+m_1y_1\\ x= a_2+m_2y_2 \end{cases}${x=a1​+m1​y1​x=a2​+m2​y2​​，也即 $m_1y_1-m_2y_2=a_2-a_1$m1​y1​−m2​y2​=a2​−a1​。

那我们就可以用扩展欧几里得算法来解这个式子。

如果这个式子无解，则原同余方程组无解。

否则的话，解出一组可行解 $(y_1,y_2)$(y1​,y2​)，代回去解出一个关于 $x$x 的可行解 $x_1$x1​，令 $m=\mathrm {lcm}(m_1,m_2)$m=lcm(m1​,m2​)。上述的方程组就等价于：

$x\equiv x_1(\,\mathrm{mod}\;m)$x≡x1​(modm)

两两合并，最后只剩下 $1$1 个方程，解出来便是答案。

模板题：[POJ 2891] Strange Way to Express Integers