欧几里得算法是求解两个数的最大公约数的算法，而扩展欧几里得算法则是求解一元线性方程 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。
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。
所以，我们可以通过矩阵的方式来求解扩展欧几里得算法：
#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 就是判断是否有整数解的条件。