前言

CRT，中国剩余定理，用于求解同余方程。
据说古代有个著名问题叫韩信点兵，数学化一下就是
x ≡ 2(mod 3)
x ≡ 3(mod 5)
x ≡ 2(mod 7)

求解

我们三个等式分开求解，最后加起来，那么如果x1是5和7的公倍数，后面加的时候就不会产生影响。
由第一个等式我们得到，x1是5和7的公倍数，且%3==2。
转化一下得到
若a是5和7的公倍数，且%3==1，那么2a就是一个合法的x，余数的可乘性。
那么要保证是5和7的公倍数，就 $*35$ ，又要保证%3==1，那么再乘以35在%3意义下的逆元就行了，最后乘以2，所以x1=35 $*({35}^{-1})*2$
同理求出x2,x3,然后x1+x2+x3就是一个合法解，最小解的话模一下最小公倍数就可以了
这其实就是中国剩余定理
对于一组同余方程

如果保证 $m_1,m_2…m_k$ 两两互质, 且令P为 $m_1,m_2…m_k$ 之积
则有结论 x ≡ ( $a_1*M_1*M_1^{-1}+a_2*M_2*M_2^{-1}+…+a_k*M_k*M_k^{-1}$ )(mod P)
其中 $M_i$ 为 $\frac{P}{m_i}$ , $M_i^{-1}$ 即 $M_i$ 在模 $m_i$ 意义下的逆元( $M_i*M_i^{-1}$ ≡1(mod $m_i$ ))
原理就和前面举的例子一样，只不过扩展了一下。
希望能对学习有帮助，谢谢。