欧几里得算法是求解两个数的最大公约数的算法，而扩展欧几里得算法则是求解一元线性方程 $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$ 就是判断是否有整数解的条件。