求解同余方程组最小整数解：
\[\left\{\begin{matrix} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \cdots \\ x\equiv a_n\pmod {m_n} \end{matrix}\right.\]设前 \((k-1)\) 个方程的特解为 \(x\)，则显然有通解 \(x+iM\ (i\in \mathbb{N})\)，其中 \(M\) 表示 \(m_1,m_2,\cdots,m_{k-1}\) 的 \(\text{LCM}\)。当然表示乘积也可以，但这样可以有效防止溢出。
考虑前 \(k\) 个方程的解，为了让所有方程满足要求，需在前 \((k-1)\) 个方程的通解里找到一个解满足第 \(k\) 个方程，不妨设为 \(x+tM\ (t\in \mathbb{N})\)。
把这个解带入进第 \(k\) 个方程得到 \(x+tM\equiv a_k\pmod {m_k}\)，移项可得 \(tM\equiv a_k-x\pmod {m_k}\)，用 \(\text{exgcd}\) 求解 \(t\)，那么可以得到前 \(k\) 个方程的一个特解为 \(x+tM\)，然后不断按照这个过程往后合并即可。本质是 \((n-1)\) 次 \(\text{exgcd}\)。
标签：mathbb,方程,pmod,text,excrt,tM,equiv From： https://www.cnblogs.com/UperFicial/p/16962290.html