本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 16:03:14

要求一堆形如

$$x \equiv k_i\pmod {p_i}$$

的同余方程的解。

设 $P = \prod p$，则

$$x = \sum k_i \dfrac P {p_i} (\dfrac P {p_i})^{-1} \bmod P$$

其中这里的逆元是模 $p_i$ 意义下的。

考虑为什么。

不难发现，对于第 $i$ 个同余方程，对于 $i \ne j$ 都有 $P/p_j \equiv 0 \pmod {p_i}$，因为里头本来就有个 $p_i$。

于是式子就剩下了当前这一项。而 $P/p_i$ 乘上其模 $p_i$ 意义下的逆元本身就是一，于是就剩下了 $k_i$。