中国剩余定理

relearn 了一遍 exCRT ，发现之前学的可能是假的（这种情况出现不止一次了 233 ）。

简单来说，中国剩余定理（以下简称 CRT ）主要用于解线性同余方程组：

\[ \begin{equation} \left\{ \begin{aligned} x \equiv a_1 \pmod{m_1} \\\\ x \equiv a_2 \pmod{m_2} \\\\ ... \\\\ x \equiv a_n \pmod{m_n} \\\\ \end{aligned} \right. \end{equation} \]

CRT

普通的 CRT 用于解决模数两两互质的情况（这个条件比较苛刻，实践中往往需要 exCRT ）。

CRT 的主要思想是构造，对于每个方程组构造一个 \(b_i\) 使得 \(b_i\) 在其他所有模数下为 0 ，仅在模 \(m_i\) 意义下为 1 。
感觉这个构造思路有点想拉格朗日插值法，那么不难得出：

\[ b_i = \prod_{i \ne j} m_j (\prod_{i \ne j} m_j)_{m_i}^{-1} \]

其中 \((\prod_{i \ne j} m_j)_{m_i}^{-1}\) 是 \(\prod_{i \ne j} m_j\) 在模 \(m_i\) 意义下的逆元。

那么整个方程组的一个解就是 \(\sum_{i=1}^n b_i a_i\) ，通解就是：

\[ x \equiv \sum_{i=1}^n b_i a_i \pmod{\prod_{i=1}^n m_i} \]

exCRT

CRT 只适用于模数两两互质的情况，因为用到了模数之间的逆元，而模数不互质是没有逆元的。

exCRT 的主要思想是两两合并，考虑 \(n=2\) 的情况：

\[ \begin{equation} \left\{ \begin{aligned} x \equiv a_1 \pmod{m_1} \\\\ x \equiv a_2 \pmod{m_2} \\\\ \end{aligned} \right. \end{equation} \]

那么此时方程组的解 \(x\) 需要满足存在 \(i, j\) 使得：

\[ x = a_1 + i m_1 = a_2 + j m_2 \]

对于右边的等式 \(a_1 + i m_1 = a_2 + j m_2\) ，是关于 \(i, j\) 的二元一次方程，
那么用扩展欧几里得解出一组解 \(i=i_0, j=j_0\) 再回代到等式中即可求得一个 \(x = x_0\) 。
而通解的话，根据 exgcd 的通解 \(i \equiv i_0 \pmod{\frac{m_2}{\gcd(m_1, m_2)}}\) ，可以得到 \(x\) 的通解：

\[ x \equiv x_0 \pmod{lcm(m_1, m_2)} \]

那么据此可以将任意两个同余方程合并为一个，也就可以通过两两合并的方式将整个同余方程组合并为一个方程。

无解的话，当且仅当 exgcd 解 \(i, j\) 的时候无解，只要有两个方程无法合并那么整个方程组都无法合并。