扩展欧几里得算法

今天开始学习数论方面的算法。这部分在 NOIP 中并不常出现，即使出现了也不会像高联这么难（。。。）。

什么是扩展欧几里得算法

所谓欧几里得算法，实际上就是辗转相除法——求两个数最大公约数的一种高效算法。而扩展欧几里得算法则是来源于于一类方程的解决：

$$ax+by=gcd(a,b)$$

这有点像是裴蜀定理的一般形式。和裴蜀定理类似，这类方程也有无数多个整数解。如何高效率地求得它的一组特解呢？

代码

procedure gcd_ex(a, b: longint; var d: longint; var x, y: longint);
begin
    if b = 0 then
    begin
        d := a;
        x := 1;
        y := 0;
        exit;
    end;
    // hl:begin #1
    gcd_ex(b, a mod b, d, y, x);
    // hl:end
    y := y-(a div b) * x;
end;

详解

乍一看，算法似乎和一般欧几里得算法很是相似：都是递归实现，参数传递过程中都体现了“辗转相除”的思想。那为什么这个算法是正确的呢？ 这里先解释一下参数：

• a：方程中的参数 a
• b：方程中的参数 b
• d：即 gcd(a,b)。由于和辗转相除法的相似性，在这里最大公约数也可以“顺便”算出。当然，去掉也无大碍
• (x,y)：方程的一组特解 (x, y)

下面解释标注了 1 的那行代码。

假设方程 $ax+by=gcd(a,b)$ 有一组特解 $(x_0,y_0)$。则有$$ax_0+by_0=gcd(a,b)$$

由最大公约数原理可知：$$gcd(a,b)=gcd(b, a\ mod\ b)$$

从而有$$ax_0+by_0=gcd(b,a\ mod\ b)$$

又方程 $bx+(a\ mod\ b)y=gcd(b,a\ mod\ b)$ 一定有整数解，设其为 $(x_1,y_1)$。则有

$$ax_0+by_0=gcd(b,a\ mod\ b)=bx_1+(a\ mod\ b)y_1$$即$$ax_0+by_0=bx_1+(a-(a\ div\ b)*b)y_1$$

即 $$a(x_0-y_1)=b(x_1-(a\ div\ b)y_1-y_0)$$

由恒等原理可知：$$x_0=y_1$$$$y_0=x_1-(a\ div\ b)y_1$$

因此，当 $a,b\neq0$ 时，$x,y$ 的值可以递归求得。递归边界为：$b=0$ 时 $x=1,y=0$。

注意到上面的算法用到了一个技巧：在递归传参数的时候将 y, x 调换了。这样做的好处是节省了一个中间变量用来储存 $y_1$，否则在计算 $y_0$ 时 $y_1$ 也被覆盖了。从而使算法更加的精简。

应用

• 计算几何中求整点的问题
• 求一元一次同余方程 $a\equiv b\pmod{m}$ 的一组特解。（即方程 $ax+my=b$ 的一组特解）

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。