扩展欧几里得算法

今天开始学习数论方面的算法。这部分在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;
    gcd_ex(b, a mod b, d, y, x); //重要
    y := y-(a div b) * x;
end;

详解

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

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

下面解释标注了重要的那行代码。 假设方程 $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$的一组特解）