关于中国剩余定理

用于处理类似的同余方程

$$
ans=left{egin{matrix}
xequiv a_{1}(mod m_{1})\
xequiv a_{2}(mod m_{2})\
......\
xequiv a_{n}(mod m_{n})
end{matrix} ight.
$$
如果整数 $m_1,m_2...m_n$ 两两互质,则对任意整数 $a_1,a_2,...a_n$ ,方程有解,并且通解可以用如下方式构造得到:

设 $M=m_1 imes m_2 imes ...... imes m_n=prod_{i=1}^{n}m_i$ ,并设 $M_i=frac{M}{m_i}$ ,设 $t_i=M_i^{-1}$ 为 $M_i$ 模 $m_i$ 的数论倒数。

在$mod M$ 的意义下通解形式为:
$$
x=(a_1t_1M_1+a_2t_2M_2+...+a_nt_nM_n)mod M
$$
可以用于计数类问题,模数非质数的情况。

原文地址:https://www.cnblogs.com/Jessie-/p/10504834.html