本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 20:51:14

exCRT 的核心就是合并两个同余方程的解。

考虑

$$ \begin{cases} x \equiv w_i \pmod {p_i} \ x \equiv w_j \pmod {p_j} \end{cases} $$

那么有

$$x = p_ik_i + w_i = p_jk_j + w_j$$

这时候可以用扩欧解出来 $k_i$ 和 $k_j$，以此还原出 $x$，然后继续合并。