Trancy

摘自某大神博客,mark一下

我们现在还有一个问题:x,y是不是确定的?答案:不是。如果x,y符合要求,那么x+bk,y-ak也符合要求。不确定的原因在于这一句:“当b=0时,我们取x=1,y=0。”实际上y可以取任何正整数。
不定方程ax+by=c
解二元一次不定方程。看起来扩展Euclid算法是不定方程的一种特殊情况,实际上呢,不定方程却是用Euclid算法解的。
对 于不定方程ax+by=c,设gcd(a,b)=d,如果ax+by=c有解,则d|c(这也是许多奥数题的切入点)。所以一旦d不是c的约数,那么 ax+by=c一定无解。当d|c时,先求出ax'+by'=d=gcd(a,b)的x'和y',则x=x'*c/d,y=y'*c/d。由上一段可知, 只要ax+by=c有一个解,它就有无数个解。
Euclid算法还可以求解同余方程ax≡b(mod m)。这其实和不定方程ax+my=b没有区别。(不定方程和同余方程一般都有范围限制,这其实也很容易解决,就不说了)

评论