exCRT

· · 个人记录

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，然后继续合并。