欧几里得算法：

定义：gcd 的意思是最大公约数，通常用扩展欧几里得算法求

原理： $gcd(a, b) = gcd(b, a \% b)$

证明：

令 $d = gcd(a, b) \Rightarrow a = m \cdot d, b = n \cdot d$

则 $m \cdot d = t \cdot n \cdot d + a \% b \Rightarrow a \% b = d \cdot (m - t \cdot n)$

$gcd(b, a \% b) = gcd(n \cdot d, (m - t \cdot n) \cdot d)$

令 $gcd(n, m - t \cdot n) = e \Rightarrow n = x \cdot e, m - t \cdot n = y \cdot e$

则 $m - x \cdot e \cdot n = y \cdot e \Rightarrow m = e \cdot (x \cdot n + y)$

由 $gcd(n, m) = 1$ 知 $gcd(e \cdot (x \cdot n + y), e \cdot x) = 1$

故 $e = 1$

故 $gcd(n \cdot d, (m - t \cdot n) \cdot d) = d$ 即 $gcd(b, a \% b) = gcd(a, b)$

边界：

当 b = 0 时 return a

可以视为 $gcd(a, 0) = a$ ，任何数都能整除 $0$

也可以视为 $gcd(a, b) = b$ ，这里的 $a$ 和 $b$ 是上一层的，满足 $a \% b = 0$

特殊情况：
当 a < b 时，a%b = a，所以在下一层 gcd(b, a%b) 中相当于把 a 与 b 交换
代码：

1	int gcd(int a,int b){ return b ? gcd(b,a%b) : a;}

扩展欧几里得算法：

丢番图方程：

有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行。

扩展欧几里得算法研究的是形如 $a \cdot x + b \cdot y = c$ 的丢番图方程的解

裴蜀定理：

对于正整数 $a$ 和 $b$ ，令 $gcd(a, b) = d$ ，则对于任意整数 $x$ 和 $y$ ，都有 $d|(a \cdot x + b \cdot y)$

证明：

令 $a = n \cdot d, b = m \cdot d$ ，则 $a \cdot x + b \cdot y = d \cdot n \cdot x + d \cdot m \cdot y$

显然 $d|(d \cdot n \cdot x + d \cdot m \cdot y)$

引理：

丢番图方程 $a \cdot x + b \cdot y = c$ 有解当且仅当 $d|c$

对于任意整数 $x$ 和 $y$ ， $a \cdot x + b \cdot y$ 的最小正值为 $gcd(a, b)$

证明：

①必要性：

由裴蜀定理，不存在整数 $x$ 和 $y$ ，使得 $d$ 不整除 $(a \cdot x + b \cdot y)$

②充分性：

要证 $a \cdot x + b \cdot y = c$ 有解，只需 $a \cdot x + b \cdot y = d$ 有解

令对于 $\forall x, y \in Z$ ， $a \cdot x + b \cdot y$ 能得到的最小正值为 $s$

由裴蜀定理， $d|s$ ，则 $d \leq s$

令 $q = \lfloor \frac{a}{s} \rfloor, p = a \% s$

则 $p = a - q \cdot (a \cdot x + b \cdot y) = a \cdot (1 - q \cdot x) - q \cdot b \cdot y = a \cdot (1 - q \cdot x) + b \cdot (-q \cdot y)$

由 $p = a \% s$ 知 $0 \leq p < s$

又 $s$ 为 $a \cdot x + b \cdot y$ 能得到的最小正值

故 $p = 0$ ，即 $s|a$

同理， $s|b$ ，即 $s|d$ ，故 $s \leq d$

综上， $s = d$

即对于 $\forall x, y \in Z$ ， $a \cdot x + b \cdot y$ 能得到的最小正值为 $d$

故 $\exists x, y \in Z$ ，使 $a \cdot x + b \cdot y = d$

即 $\exists x, y \in Z$ ，使 $a \cdot x + b \cdot y = c$

扩展欧几里得算法：

通常将求解 $a \cdot x + b \cdot y = c$ 转化为求解 $a \cdot x + b \cdot y = gcd(a, b)$ ，得解后乘上 $\frac{c}{gcd(a, b)}$ 即可

令
$a \cdot x_1 + b \cdot y_1 = gcd(a, b)$

$b \cdot x_2 + (a \% b) \cdot y_2 = gcd(b, a \% b)$

由 $gcd(a, b) = gcd(b, a \% b)$ 知

$a \cdot x_1 + b \cdot y_1 = b \cdot x_2 + (a \% b) \cdot y_2$

$= b \cdot x_2 + (a - b \cdot \lfloor \frac{a}{b} \rfloor) \cdot y_2 = a \cdot y_2 + b \cdot (x_2 - \lfloor \frac{a}{b} \rfloor \cdot y_2)$

故 $x_1 = y_2, y_1 = (x_2 - \lfloor \frac{a}{b} \rfloor \cdot y_2)$

如此递归直至边界情况

边界：

当 $b = 0$ 时， $gcd(a, b) = a$ （任何数都能整除 $0$ ）

$a \cdot x + b \cdot y = a \cdot x = gcd(a, b) \cdot x$

若使 $a\*x + b\*y = gcd(a, b)$ ，只需 $x = 1$ ， $y$ 可以为任何值，通常设为 $0$ ，减少溢出的风险

$y$ 的多值对应方程的多解

通解：

对于对于第一个解 $x_0$ 和 $y_0$ ，其他解可以表示为 $x_0 + \frac{b}{d} \cdot k$ 和 $y_0 - \frac{a}{d} \cdot k$

推导：

令 $a \cdot (x + m) + b \cdot (x - n) = d$

$\Rightarrow a \cdot m = b \cdot n \Rightarrow \frac{m}{n} = \frac{b}{a}$

因 $gcd(a, b) = d$ ， $m$ 和 $n$ 均为整数

故 $m$ 和 $n$ 的最小值分别为 $\frac{b}{d}$ 和 $\frac{a}{d}$

若要求其中一个解为正整数，可在得到负解后用通解转化为正数

代码：

void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int z=x;
    x=y,y=(z-a/b*y);
}

易错点：

算法中存在乘法，有溢出的风险，应见机开 long long

例题：

洛谷4549 裴蜀定理

洛谷1516 青蛙的约会

洛谷3951 小凯的疑惑

洛谷1082 同余方程