拓展中国剩余定理

· · 算法·理论

简介

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

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)。