模数非互质的同余方程组（非互质版中国剩余定理）

• hqsha 发布于
• 1461 收藏

之前介绍到的中国剩余定理只能求解模数两两互质的同余方程组。    那么，模数如果不一定两两互质的情况应该怎么求呢？    下面介绍通过合并方程的方法来解决问题（要用到扩展欧几里德算法）。      顾名思义，合并方程就是把所有的同余方程组合并成一个。    举个例子，合并同余方程组  x%A=a  ①                               x%B=b   ②        现...