中国剩余定理

用于求解线性同余方程组

• 计算所有模数乘积：${\displaystyle M=\mathrm{\Pi }{m}_i}$

• 对于第 $i$ 个方程，计算 $c_i=\frac{M}{m_i}$

• 计算 $c_i$ 在摸 $m_i$ 意义下的乘法逆元 $c_i^{-1}$

• ${\displaystyle x=\sum _{i=1}^n{r}_i{c}_i{c}_i^{-1}}$

  P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷