今天开始学习数论方面的算法。这部分在 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;
1 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)

下面解释标注了 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$ 的一组特解)