扩展欧几里得

拓展欧几里得

简单的说,就是求关于$x$,$y$的方程$ax + by = gcd(a,b)$ 的所有整数解
现在我们令$g = gcd(a,b)$
则方程变成了$ax + by = g$
假如我们现在知道了这个方程的一个特解$x_0$,$y_0$,我们就可以用一种方法求出所有的整数解。

说的比较模糊,现在整理一下。
上面提到了两个问题

  1. 怎么求出这个特解?
  2. 怎么由特解推出其它的所有解?

求特解

我们知道,欧几里得公式可以由这个式子表示:
$gcd(a, b) = gcd(b, b \%a) $
不断往下连等,直到$b = 0$,此时a即为最大公约数
那么我们来讨论另一个问题,下面两个式子有没有关系呢?

如果看这篇博客的你还没接触过拓展欧几里得,那么可能你还不知道现在在干什么。
那么,我可以告诉你,只要找出$x_1$和$x_2$的关系、$y_1$和$y_2$的关系,我们就能求出方程$a \cdot x+b \cdot y = g$的一个特解

回到刚才那个问题,很显然,两个等式右边就是欧几里得的公式
那么我们就能得出
$a \cdot x_1 + b \cdot y_1 = b \cdot x_2 + (a \%b) \cdot y_2 $
其中a%b可以换成$a - (a / b) \cdot b $
式子变成了
$a \cdot x_1 + b \cdot y_1 = b \cdot x_2 + (a - (a / b) \cdot b) \cdot y_2 $
因为我们要找$x_1$ $y_1$ 和$x_2$ $y_2$的关系
我们可以用待定系数法,按照这种方法把右边化成$b \cdot (x_2 - (a / b) \cdot y_2) + a \cdot y_2 $
则等式变成了
$a \cdot x_1 + b \cdot y_1 = a \cdot y_2 + b \cdot (x_2 - (a / b) \cdot y_2) $
(上面的过程最好动手演算)
好,我们现在得出了下面两个等式:
$x_1 = y_2$(等式两边a的系数相同)
$y_1 = x_2 - (a / b) \cdot y_2$ (等式两边b的系数相同)
也就是说,我们知道了方程$b \cdot x_2 + (a \%b) \cdot y_2 = g(b,a \%b)$ 的解$x_2, y_2$,就可以得到方程$a \cdot x_1 + b \cdot y_1 = g(a,b)$ 的解$x_1$, $y_1$了,这个小问题告一段落。

对于方程,我们可以不断的往下变成 ,按照欧几里得的过程,$b$会变成0,即此时方程 因为,变成了,还是由欧几里得算法得到,此时$a$就等于$gcd(a,b)$,所以得到由原方程往下推了不知道多少次的方程$a \cdot x = gcd(a,b)来说$,得到一个解x = 1, y = 0。现在得到了这个方程的解,利用上一个小问题挣出的结论,就可以得出原方程的一个特解。

OK,这个问题解决了。

怎么利用特解推出其他所有整数解?

先说结论:
对于关于x,y的方程$a \cdot x + b \cdot y = g $来说,让$x$增加$b/g$,让$y$减少$a/g$,等式两边还相等。(注意一个增加一个减少)
为什么呢?
这个很容易得到,我们算一下即可。
让$x$增加$b/g$,对于$a \cdot x$这一项来说,增加了$a \cdot b / g$,可以看出这是a,b的最小公倍数同样,对于$b \cdot y$这一项来说,$y$ 减少 $a/b$,这一项增加了$a \cdot b / g$,同样是a,b的最小公倍数。
可以看出,这两项一项增加了一个最小公倍数,一项减少了一个最小公倍数,加起来的和仍然等于g。
这样我们就明白了,其实这种操作就是增加一个最小公倍数,减少一个最小公倍数,这样来改变x,y的值,来求出所有x,y的通解的。

那为什么改变的是最小公倍数而不是更小的数呢?因为是最小公倍数呀..不会再找到更小的值了,这个自行体会吧。

如何求解方程

到这里为止,开头提出的两个问题都已经解决。
也就是说,对于方程$a \cdot x + b \cdot y = gcd(a, b)$,我们能找出所有符合条件的解了。而且,还可以告诉你,这个方程是一定有无数个解的。

那么来一个更一般的问题,对于方程$a \cdot x + b \cdot y = c$来说,它的解怎么求呢?
答:如果$c % gcd(a,b) != 0$,即c不是gcd的整数倍,则无解。
如果$c % gcd(a, b) == 0$ 且$ c / gcd(a, b) = t$,那么求出方程 $a \cdot x + b \cdot y = gcd(a, b)$的所有解$x$,$y$,将$x$, $y$乘上$t$,对应的$x’$,$y’$即是方程$a \cdot x + b \cdot y = t \cdot gcd(a, b)$的解
很好理解,就不解释了,仔细看上面的这段话就能理解

扩展欧几里得代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void e_gcd(int a, int b, int &gcd, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
gcd = a;
}
else
{
e_gcd(b, a % b, gcd, y, x);
y -= x \cdot (a / b)
}
}

作者:life_bre
来源:CSDN
原文:https://blog.csdn.net/sdutstudent/article/details/78795643?utm_source=copy
版权声明:本文为博主原创文章,转载请附上博文链接!