CRT和ExCRT是用来求解如下的线性同余方程组的：
\[
x\equiv a_1\ (mod\ p_1)\x\equiv a_2\ (mod\ p_2)\……\x\equiv a_n\ (mod\ p_n)\\]
先考虑特殊一点的情况：任意的pi互质。可以用CRT解决。
CRT的核心思想就是构造。
考虑构造出每一个同余方程的解，并且使它们可以直接合并成最终答案，即两两之间互不影响。
\[ 令：\PP=\sum_{i=1}^n{p_i}\Pi=PP/pi\Ti为方程：Ti*Pi\equiv 1\ (mod\ p_i)\ 的解\那么最后ans=\sum_{i=1}^n a_i*T_i*P_i \]
原文：https://www.cnblogs.com/Bhllx/p/10658643.html