考虑递推
假设对于前 \(i\) 个线性同余方程,我们得到了 \(x\) 的一个解 其通解显然为 \(x+k*M_i\)
其中 \(M\) 为前 \(i\) 个方程的最小公倍数
对于第 \(i+1\) 个方程,我们需要求出 \(x+t*M_i \equiv a_{i+1} (mod \,\, m_{i+1})\) 中的t值
exgcd
求解同余方程即可
这样推n次即可得到最终答案
标签:方程,CRT,公倍数,扩展,即可,同余 From: https://www.cnblogs.com/UNowen/p/17484019.html