在某些题目中由于题目的性质或出题人的恶意，需要求解答案模一个非质数的情况。这时就很可能需要利用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只需要保证互质，并不一定是质数。如果不是质数则逆元不能用费马小定理求解。
之前一直不懂…现在觉得好显然…(大概是看着名字长就觉得太难就没学)