crt

· · 个人记录

要求一堆形如

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。