【模板】扩展中国剩余定理（EXCRT）题解

思路

设已经合并的若干条同余式等价于

现在加入 $x\equiv b\pmod a$。令 $x=r+Mk$，就需要解

记 $g=\gcd(M,a)$。题目保证原方程组有解，因此 $g\mid(b-r)$。两边同时除以 $g$ 后得到

$M/g$ 与 $a/g$ 互质，可以用扩展欧几里得算法求出 $M/g$ 在模 $a/g$ 意义下的逆元，从而求得最小非负的 $k$。新的模数为

再把 $r+Mk$ 归一化到这个模数下即可。

第一档中模数依次整除。由于数据保证有解，最后一条同余式已经蕴含前面的所有同余式，所以直接输出 $b_n\bmod a_n$。

第二档中模数两两互质，可以使用普通中国剩余定理：对模数乘积 $P$，令 $P_i=P/a_i$，求 $P_i$ 对 $a_i$ 的逆元，将 $b_iP_iP_i^{-1}$ 求和后对 $P$ 取模。

做法

初始令 $M=1,r=0$。按输入顺序逐条合并同余式：

1. 用扩展欧几里得算法求 $g=\gcd(M,a_i)$ 以及相应系数。
2. 在线性同余式中求出 $k$ 对 $a_i/g$ 的最小非负剩余。
3. 更新 $r\leftarrow r+Mk$，并对新模数 $M(a_i/g)$ 归一化。
4. 更新 $M\leftarrow M(a_i/g)$。

所有同余式处理完成后输出 $r$。乘法使用 128 位整数完成，避免中间结果溢出。

正确性可以用归纳法证明。初始状态表示所有整数。假设当前的 $r,M$ 恰好描述已经处理的同余式的全部解，线性同余式求出的 $k$ 恰好使 $r+Mk$ 同时满足新同余式；而 $k$ 在模 $a_i/g$ 意义下唯一，所以合并后的解恰好构成模 $\operatorname{lcm}(M,a_i)$ 的一个剩余类。归纳可知最终 $r$ 满足全部同余式，归一化后就是最小非负解。

复杂度

每次合并只进行一次扩展欧几里得运算，时间复杂度为 $O(n\log A)$，其中 $A=\max a_i$；额外空间复杂度为 $O(1)$。