前言

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$))
原理就和前面举的例子一样，只不过扩展了一下。
希望能对学习有帮助，谢谢。