前言

扩展偶极里德算法(Extended Euclidean algorithm, EXGCD), 用于求 $ax+by=gcd(a,b)$ 的一组可行解。

在面试中，面试官可能出一些看似是智力题的问题：有一个3升的杯子A和5升的杯子B，给你无限的水，如何倒出4升的水。

可能思路比较直观：

先装满A，全部倒入B中
再装满A，将B装满，此时A中还剩下1L，B中有5L水
将B中的水全部倒掉，此时只有A中有1L水，倒入B中
将A再次装满，全部导入B中，此时B中有4L水

但是，很容易发现，这个过程似乎并不是唯一的，我们还可以这样：

先装满B，将B中水倒入A中装满A。此时A中有水3L，B有水2L。
将A中的水全部倒出，然后把B中的水全部倒入A，此时A有2L水，B为空。
再将B装满水，从B向A倒水直至满，此时A中有3L，B有4L水。
把A中水全倒了，我们就有4L水了。

可以看到，这个倒水装水的过程并不是唯一的，用数学形式化这两个过程可以发现：

+A表示将A装满， +B表示将杯B装满; -A表示将A中3L水倒出，-B表示将B中5L水倒出

$A + A - B + A = 4L \\ B - A + B - A = 4L$

使用公式表示倒水、装水的这个过程，我们还能发现一个特点：我们一直都在杯满时倒水、杯空时装水。当杯只装一半水时，我们只进行转移操作——将一个杯中的水转移到另一个杯子里。

那么我们就可以从两个视角（假设只有两种杯子）来看到倒水问题了：

不停的往A加水，转移到B中；A只要不为空就向B转移水，B只要满了就全部倒掉，最后有k(目标数)升水
不停的往B加水，转移到A中；B只要不为空就向A转移水，A只要满了就需要立即倒掉，最后留有k(目标数)升水

$mA \% B= k,\text{ m}\in [1, +\infin] \\ n B \% A = k, \text{ n}\in [1, +\infin]$

当 $A=3$ 、 $B=5$ 时， $3m\%5=4$ ，如果能找到这样一个m使得等式成立，则倒出目标数量水的意图就能达到。

1. 扩展欧几里得算法

将上面的倒水问题再形式化一下：用容积分别为a和b的水杯量出体积为c的水，相当于求解方程 $a\cdot x\text{ mod }b = c$ 。

如果a, b互质，可以保证问题有解。
如果 $c\coloneqq gcd(a, b)或者c\coloneqq k\cdot gcd(a, b)$ 时，可以用扩展欧几里得算法求解 $x$

注意到，如果a和b互质，则gcd(a,b)=1，那么第二点也必然成立。因此只要c不等于 $k\cdot gcd(a,b)$ ，那么就无法找到一个 $x$ ，能够满足 $a\cdot x\text{ mod }b = c$

用扩展欧几里得算法公式来表示：

$ax+by=gcd(a,b) \\ 或:(ka)x+(kb)y = k\cdot gcd(a,b)$

#include <iostream>
using namespace std;

// 扩展欧几里得算法
int Exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int d = Exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a/b) * y;
    return d;
}

int main() {
    int x, y;
    int a, b;
    a = 3, b = 5;
    int k = 4;
    cout << "GCD: " << Exgcd(a * k, b * k, x, y) << endl;
    cout << "x: " << x << '\t' << "y: " << y << endl;
    return 0;
}