标签：剩余 1p pmod 定理 exgcd ExCRT mathrm equiv

更新日志

2024/12/11：开工。

---

概念

同中国剩余定理，但模数两两不相同。

求解。

思路

我们先考虑两个方程如何解决。

\[\begin{cases}x\equiv r_1\pmod {m_1}\\x\equiv r_2\pmod {m_2}\end{cases}\\ \Rightarrow x=m_1p+r_1=m_2q+r_2\\ \Leftrightarrow m_1p-m_2q=r_2-r_1 \]

其中 \(m_1,m_2,r_1,r_2\) 均为已知量，所以这就是一个普通的线性不定方程，使用 \(\mathrm{exgcd}\) 解决即可。

注意判断是否有解，详见 \(\mathrm{exgcd}\)。

然后我们考虑多个方程组，两两合并即可。

模板

例题

代码

前注：非题解，不做详细讲解

标签：剩余,1p,pmod,定理,exgcd,ExCRT,mathrm,equiv
From： https://www.cnblogs.com/HarlemBlog/p/18599291