CRT

用于求解类似
$$
\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.
$$
其中，$\forall i, j, ~ (m_i, m_j) = 1$

设 $M = \prod_{i = 1}^n m_i, ~ M_i = \frac{M}{m_i}$，再设 $M_it_i \equiv 1 \pmod{m_i}$，其中 $1 \le i \le n$

则可构造一解 $x = \sum\limits_{i = 1}^n a_iM_it_i$，任意解 $x_0 = x + k \times M$

ExCRT

用于求解类似
$$
\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.
$$
其中，不一定满足 $\forall i, j, ~ (m_i, m_j) = 1$

考虑两个两个处理，然后合并

现在先考虑方程
$$
\left\{
\begin{aligned}
&x \equiv a_1 \pmod{m_1} \\
&x \equiv a_2 \pmod{m_2}
\end{aligned}
\right.
$$
将同余去掉，再进行变换
$$
\left\{
\begin{aligned}
&x = a_1 + k_1m_1 \\
&x = a_2 + k_2m_2
\end{aligned}
\right. \\
\Rightarrow k_1m_1 - k_2m_2 = a_2 - a_1
$$

那么此时若 $(m_1, m_2) | (a_2 - a_1)$ 则有解，反之则无解

当然这时就可以用 $ExGCD$ 直接求解，但接下来把它化成逆元的形式会更容易解开也更不耗时

令 $d = (m_1, m_2)$，则
$$
\begin{aligned}
\frac{k_1m_1}d - \frac{k_2m_2}d &= \frac{a_2 - a_1}d \\
\frac{k_1m_1}d &\equiv \frac{a_2 - a_1}d \pmod{\frac{m_2}d} \\
k_1 &\equiv inv (\frac{m_1}d, \frac{m_2}d)\frac{a_2 - a_1}d \pmod{\frac{m_2}d} \\
k_1 &= inv (\frac{m_1}d, \frac{m_2}d)\frac{a_2 - a_1}d + t\frac{m_2}d \\
\end{aligned}
$$
其中 $inv (x, p)$ 表示 $x$ 在模 $p$ 意义下的逆元

此时将 $k_1$ 代入 $x = a_1 + k_1m_1$，则有
$$
x \equiv a_1 + m_1 \times inv(\frac{m_1}d, \frac{m_2}d)\frac{a_2 - a_1}d \pmod{\frac{m_1m_2}d}
$$
然后合并 $n - 1$ 次即可

Ex-ExCRT

If we suppose that our equation set is something like this:
$$
\left\{
\begin{aligned}
&b_1x \equiv a_1 \pmod{p_1} \\
&b_2x \equiv a_2 \pmod{p_2} \\
&… \\
&b_nx \equiv a_n \pmod{p_n}
\end{aligned}
\right.
$$
then we need to change the way we process the equations

Suppose that we have got the answer of the first $i - 1$ congruence equations, we call it $ans$. And suppose $M$ to be the least common multiple of $\{p_1,p_2, p_3, …, p_n\}$, then obviously, the answer of the first $i$ congruence equations $ANS$ should be $ans + kM (k \in \mathbb Z)$. Let us start to derive:
$$
\begin{aligned}
&ANS = ans + Mx \\
&\Rightarrow b_i (ans + Mx) \equiv a_i \pmod{p_i} \\
&\Rightarrow b_iMx \equiv a_i - b_i \times ans \pmod{p_i} \\
&\Rightarrow b_iMx + p_iy = a_i - b_i \times ans
\end{aligned}
$$
Apparently, we can use $ExCRT$ to solve the last equation.