题解

思路

题目给出了方程组

并保证所有模数两两互质。根据中国剩余定理，模 $M=\prod a_i$ 意义下恰有一个解，因此只需构造区间 $[0,M)$ 内的解。

做法

小乘积

当 $M\le 10^6$ 时，可以从 $0$ 到 $M-1$ 依次枚举 $x$，检查它是否满足全部同余式。中国剩余定理保证一定能在这个区间内找到唯一答案。

模数均为质数

令 $M_i=M/a_i$。当 $a_i$ 为质数时，由费马小定理，$M_i$ 在模 $a_i$ 意义下的逆元为

于是可以直接计算中国剩余定理的构造式。

一般情形

对于任意两两互质的模数，用扩展欧几里得算法求出 $M_i$ 在模 $a_i$ 意义下的逆元 $t_i$。答案为

中间乘积可能远超 64 位整数范围，因此计算乘积与模加法时使用 128 位整数。

正确性证明

对任意一个下标 $j$，当 $i\ne j$ 时，$M_i$ 含有因子 $a_j$，所以第 $i$ 项模 $a_j$ 为 $0$；而第 $j$ 项满足 $M_jt_j\equiv1\pmod {a_j}$，故总和模 $a_j$ 恰为 $b_j$。因此构造出的 $x$ 满足全部同余式。

由于模数两两互质，中国剩余定理保证模 $M$ 的解唯一。将构造结果规范到 $[0,M)$ 后，所得数就是最小非负解。

复杂度

满分算法对每个模数执行一次扩展欧几里得算法：

• 时间复杂度为 $O\!\left(\sum_{i=1}^{n}\log a_i\right)$；
• 空间复杂度为 $O(1)$。