拓展中国剩余定理

简介 ​

拓展中国剩余定理被用于解决线性同余方程组问题，每一个同余方程形如

$$x\equiv b_i\pmod{a_i}$$

中国剩余定理可以在 $a_i$ 两两互质的情况下解决这一问题，拓展中国剩余定理则对于有解的方程组均可以解决。由于拓展中国剩余定理使用范围严格强于原定理，且时间复杂度相同，所以一般使用拓展中国剩余定理。

算法流程 ​

该算法的核心步骤为合并两个方程。

假设有 $x\equiv b_1\pmod{a_1}$ 和 $x\equiv b_2\pmod{a_2}$，那么，

$$x=k_1a_1+b_1=k_2a_2+b_2$$

移项得到，

$$k_1a_1-k_2a_2=b_2-b_1$$

注意到这是二元线性同余方程的形式，使用拓展欧几里得算法可以求出一组可行解。

那么令 $a=\text{lcm}(a_1,a_2),b=k_1a_1+b_1$，那么原方程组的通解表示为

$$x\equiv b\pmod a$$

这就完成了合并的步骤。

若要合并多个方程组，可以逐个进行合并，求解 $n$ 组方程的时间复杂度为 $O(n\log n)$。