poj 2891 Strange Way to Express Integers (扩展欧几里得算法解一般线性同余方程组)

题目链接

题意:给出k个方程,形式为 x%a1==r1,求最小的正数x,无解输出-1.

思路:首先很容易让人联想到crt.

然而crt的使用条件是,所有的m(也就是这道题中的a)两两互质,这道题并不满足,因此不能使用crt.

X mod m1=r1
X mod m2=r2



X mod mn=rn

首先,我们看两个式子的情况
X mod m1=r1……………………………………………………………(1)
X mod m2=r2……………………………………………………………(2)
则有
X=m1*k1+r1………………………………………………………………(*)
X=m2*k2+r2
那么 m1*k1+r1=m2*k2+r2
整理,得
m1*k1-m2*k2=r2-r1
令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1),原式变成
ax+by=m
熟悉吧?此时,因为GCD(a,b)=1不一定成立,GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立,则方程无解。(理论依据:裴蜀定理
否则,继续往下。

解出(x,y),将k1=x反代回(*),得到X。
于是X就是这两个方程的一个特解,通解就是 X’=X+k*LCM(m1,m2)
这个式子再一变形,得 X’ mod LCM(m1,m2)=X
这个方程一出来,说明我们实现了(1)(2)两个方程的合并。
令 M=LCM(m1,m2),R=r2-r1 注意这里原博客写错了,应该为R=x*m1+r1
就可将合并后的方程记为 X mod M = R。

然后,扩展到n个方程。
用合并后的方程再来和其他的方程按这样的方式进行合并,最后就能只剩下一个方程 X mod M=R,其中 M=LCM(m1,m2,…,mn)。
那么,X便是原模线性方程组的一个特解,通解为 X’=X+k*M。

如果,要得到X的最小正整数解,就还是原来那个方法:

X%=M;
if (X<0) X+=M;

参考博客

这篇题解是我看了那么多讲得最清楚的一篇了….虽然证明的那个地方笔误了。。。好在对照下代码就看出来了(个鬼,我问了好几个人,想到现在。。。最后发现是笔误。好气啊

这道题实际上给出了解线性同余方程组的一般做法(即,不要求所有的m两两互质)

这种做法的理论依据是扩展欧几里得算法,和中国剩余定理没什么关系…

不过既然都是解线性同余方程组。。。非要把这种做法叫什么ex_crt…我也不是很反对….

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz