在某些题目中由于题目的性质或出题人的恶意，需要求解答案模一个非质数的情况。这时就很可能需要利用CRT进行求解。
$$
\begin{equation}
\begin{cases}
x\equiv a_1 (\mod n_1)\\
x\equiv a_2 (\mod n_2)\\
x\equiv a_3 (\mod n_3)\\
\vdots\\
x\equiv a_k (\mod n_k)
\end{cases}
\end{equation}
$$
当$n_k$互质时可以进行求解。
首先求出$n_k$的积$n$。我们发现如果对于每一个等式都可以求出一个$b_i$使得$b_i\equiv 1(\mod n_i)$且$b_i\equiv 0(\mod n_{k!=i})$。那么答案显然是$\sum{b_i\times a_i}\mod n$。
求解过程就是把$c_i=\prod_{k!=i}{n_k}$和它在模$n_i$意义下的逆元${c_i}^{-1}$求出来。那么显然$c_i\times {c_i}^{-1}$符合上述要求。就做完了。
如果是在题目中答案要模一个合数，首先对需要模的合数进行质因数分解然后如此操作即可。如果某个质因数的次数大于一，那么就保留这个质因数次数当一个$n_k$即可，毕竟只要保证每个$n_i$互质即可。
但是要注意的是，由于$n_k$只需要保证互质，并不一定是质数。如果不是质数则逆元不能用费马小定理求解。
之前一直不懂…现在觉得好显然…(大概是看着名字长就觉得太难就没学)