欧几里得算法是求解两个数的最大公约数的算法,而扩展欧几里得算法则是求解一元线性方程 $ax+by=c$ 的整数解的算法,是欧几里得算法的升级版,也是提高的数论内容中的重要算法之一。

这个算法的原理是利用欧几里得算法求解最大公约数的过程中,不断地更新 $x$ 和 $y$ 的值,直到求解出整数解。具体的过程如下:

设 $a$ 和 $b$ 为两个整数,$d = \gcd(a, b)$,则有 $ax+by=d$。我们可以通过欧几里得算法求出 $d$。

设 $a = b \times k + r$,则有 $d = \gcd(b, r)$,且 $d = bx’+ry’$。将 $r$ 代入,有 $d = bx’+(a-bk)y’$,整理得 $d = ay’+b(x’-ky’)$。因此,我们可以通过递归的方式求解 $x$ 和 $y$。

1
2
3
4
5
6
7
8
9
10
11
LLI exgcd(LLI a,LLI b,LLI &x,LLI &y){
if(b==0){
x=1,y=0;
return a;
}
LLI d=exgcd(b,a%b,x,y);
LLI z=x;
x=y;
y=z-a/b*y;
return d;
}

这个算法的时间复杂度是 $O(\log \min(a,b))$,空间复杂度是 $O(\log \min(a,b))$。

以上是理解扩展欧几里得算法过程的递归方式。实际上还有一种矩阵的解释,个人认为这种方式更加直观写起来也更容易。

我们知道,$a\bmod b=a-b\lfloor {a \over b}\rfloor$,所以我们可以将 $a$ 和 $b$ 的关系用矩阵表示:

这实际上是应用了一次辗转相除法,将 $a$ 和 $b$ 的关系转化为了 $b$ 和 $a\mod b$ 的关系。
不妨将第$n$次迭代的矩阵记为 $A_n$,那么我们知道

其中 $a_n$ 和 $b_n$ 分别是 $a$ 和 $b$ 的第 $n$ 次辗转相除法的结果。并且最终的结果是

其中 $d$ 是 $a$ 和 $b$ 的最大公约数。

中的 $x1$ 和 $x2$ 就是我们要求的 $x$ 和 $y$。

所以,我们可以通过矩阵的方式来求解扩展欧几里得算法:

1
2
3
4
5
6
7
8
9
10
#define T3I tuple<int,int,int>

T3I exgcd(int a,int b){
int x1=1,x2=0,x3=0,x4=1,c;//初始化为单位矩阵
while(b){
c=a/b;
tie(x1,x2,x3,x4,a,b)=make_tuple(x3,x4,x1-x3*c,x2-x4*c,b,a-b*c);
}
return make_tuple(x1,x2,a);
}

总之,这样就求出了 $ax+by=\gcd(a,b)$ 的整数解 $(x,y)$。那么,如果我们要求解 $ax+by=c$ 的整数解,只需要将 $c$ 除以 $\gcd(a,b)$,然后将 $x$ 和 $y$ 同时乘以这个商即可。所以也可以得到 $\gcd(a,b)$ 是否整除 $c$ 就是判断是否有整数解的条件。