中国剩余定理(crt)学习记录

· · 个人记录

对于这样一个方程组:

x \equiv a1 (\mod mod1)\\ x \equiv a2 (\mod mod2)\\ x \equiv a3 (\mod mod3)\\ \cdots\cdots\\ x \equiv an (\mod modn) \end{cases}

设一个数 MUL = \Pi_{i=1}^{n} modi
MODi = \frac{a}{modi}
CiMODi 在模 modi 意义下的逆元
解: x = \Sigma_{i=1}^{n} ai \cdot MODi \cdot Ci
注解:因为 CiMODi 的逆元 ,MODi \cdot Ci \equiv 1 (\mod modi),乘上ai,就变为 ai \cdot MODi \cdot Ci \equiv ai (\mod modi)
最后 ans = x \mod MUL