前置

想学明白扩展欧几里得先要搞懂欧几里得算法（辗转相除法）。只会模板是不行的，需要把原理搞懂。
要不然就会像我一样，时隔多年又回来重学/(ㄒoㄒ)/~~

扩展欧几里得用途

• 判断方程ax+by=m是否有解
• 求ax+by=m的任意一组解、通解、最小整数解
• 求逆元

裴属定理

对于整数a、b，一定存在整数x、y使得ax+by=gcd(a,b)。

代码详解和证明

先找到边界b=0的时候，此时可以得到一组解
$x=1,y=0 \quad \longrightarrow \quad 1 \times a + 0 \times b = gcd(a,b)$

由于是递归过程，所以我们预设了一个边界的答案，以此来推导上一层的答案。

$x,y表示本层，x\prime,y\prime表示下一层$ 。(注意递归中是用下一层求本层的)

当$b\not=0$时，
$$ ax + by = gcd(a, b) = gcd(b, a \% b) $$

根据欧几里得算法替换$a,b$。同时$x,y$会改变，用$x\prime,y\prime$表示
$$ b x\prime + (a \% b) y\prime = gcd(b, a \% b) \\ b x\prime + (a - \lfloor{\frac{a}{b} }\rfloor b)y\prime=gcd(a,b) \\ b x\prime + a y\prime - \lfloor{\frac{a}{b}}\rfloor b y\prime=gcd(a,b)\\ a y\prime + b(x\prime - \lfloor{\frac{a}{b}}\rfloor y\prime) = gcd(a,b) = ax+by $$

得到两个相邻层之间的关系:
$x = y\prime, y = x\prime - \lfloor{\frac{a}{b}}\rfloor y\prime\\$

为了简化代码，交换$x\prime,y\prime$
$$ a x\prime + b(y\prime - \lfloor{\frac{a}{b}}\rfloor x\prime) = gcd(a,b) = ax+by $$可以得到

$x = x\prime, y = y\prime - \lfloor{\frac{a}{b}}\rfloor x\prime \\$

通解和最小整数解

扩展欧求出的 $x,y$ 为方程 $ax + by = gcd(a, b)$ 的解

$\left\{ \begin{aligned} x_0 = \frac{x*m}{gcd(a,b)} \\ \quad y_0 = \frac{y*m}{gcd(a,b)} \\ \end{aligned} \right. $

$x_0,y_0$ 是 $ax + by = m$ 的一组解

通解

$x$ 可以左右平移变化，$y$ 随之变化

$$ a(x_0 + u) + b(y_0 + v) = m\\ a x_0 + b y_0 + au + bv = m\\ 即au + bv = 0 \quad ① $$
那么$u = b, v = -a$，意思是 $x$ 每增加 $b$ ，$y$ 就要减少 $a$

但 $x$ 的每次最小变化单位并不一定是 $b$ ，①式中 $a$ 和 $b$ 如果存在公约数可以除掉。
那么 $x$ 的最小变化单位是$\frac{b}{gcd(a,b)}$

$通解:\left\{ \begin{aligned} x_1 = x_0 + k\frac{b}{gcd(a,b)} \\ \quad y_1 = y_0 - k\frac{a}{gcd(a,b)} \\ \end{aligned} \right. ，k \in Z $

最小正整数解：

设 $t = \frac{b}{gcd(a,b)}$

$x = (x_1 \% t + t) \% t$

扩展欧

#include<iostream>
using namespace std;

void exgcd(int a,int b,int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;   // y初值可为任意数
        return;
    }
    exgcd(b,a%b,y,x);   // 交换之后 x = y′, y = x′
    y = y - a/b*x;
    return;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a,b,x,y;
        cin >> a >> b;
        exgcd(a,b,x,y);
        cout <<x <<' '<<  y << endl;
    }
}

https://blog.csdn.net/weixin_43872728/article/details/107289833
基础课评论区