阅读时间比较困难
这是数论的第二篇，在和。这篇文会从 GCD 从问题出发，探索扩展欧几里得算法。
看完标题，也许你有疑问。？为了解决欧几里算法，这里的 GCD 是指 Greatest Common Divisor 即，而不是 iOS 中的 Grand Central Dispatch ? 。所以这个分享是关于算法的。
欧几里得算法（GCD）
求 GCD 欧几里得算法被认为是数论中最常用的算法，这是我们在高中学到的。
用一句话就能说清楚欧几里得算法的基本原理：。
为什么能这样求？这里可以简单证明:
假设 a, b (a > b) 两个数的一个公约数是 t ，则有
因为 a > b ，设 a = k × b r ，即 r = a mod b ，将 a、b 代入展开可得：
由于 (n - k × m) × t 一定是整数，所以 a、b 的公约数 t 也是 r 约数。所以，如果我们递归求解 a mod b 也就是 a % b ，就可以得到 a、b 最大公约数 GCD 什么时候递归结束？ a % b == 0 因为在这个过程中，如果 a mod b 无法求得正整数 r 按照上述规定，不能继续拆分。
# python def gcd(a, b): return a if b == 0 else gcd(b, a % b)// C int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }这里还有一句话，a、b 两数的最大公倍数 LCM(a, b) = a * b / GCD(a, b) 。这里不证明自己对谷歌感兴趣。
头条笔试题
上个月在脉脉上看到一道头条校招的笔试题，看评论说是“地狱难度”的，我们通过这道题来延伸说一下。先来看下这题的题面：
有一个由电容器组成的计算器，每个电容器组件都有最大容量值(正整数)。对于单个电容器，有以下操作说明:
现在已知有两个电容，其最大容量分别为 a 和 b，初始状态是电量值 0，希望某个电容(无论哪一个)中的电量值等于某一列的操作 c （c也是正整数)，这些列操作中使用的最少指令条数被记录为 ，无论如何操作，都不可能完成，此时定义 M = 0。
显然，每组都确定了 ,,，会有一个 与之对应。
这里需要输入的是 a、b、c ，给出两个例子，例如 a = 3, b = 4, c = 2 ，则最少需要 4 完成指令。
说明:最大容量为 3 的是 A 另一个是另一个是 B 号电容，相应的操作是 （充电 A）=> （转移 A -> B） => （充电 A）=> （转移 A -> B） ，这样 A 就是目标的 2 电量。
第二个样例 a = 2, b = 3, c = 4，由于 a 和 b 无法达到目标电量 4，所以输出 0 代表无解。
当我们得到这个问题时，第一反应是模拟三个指令，然后使用它 BFS 只要任何情况达到目标，广度优先搜索找到答案 c 值停了下来。但标题中给出了数据量
简要分析
首先，从笔试的角度来看，由于笔试中会有数据范围的测试，这个问题给出的数据范围可能是这样的：
0<a,b,c<10^5(50%) 0<a,b,c<10^7(30%) 0<a,b,c<10^9(20%)因此，如果没有任何想法和数论基础，我建议使用它 BFS 直接写一版暴力至少可以通过 > 50% 从而获得一定的分数。(其实这就是 OI 得分赛制，没有想法先暴力抢分)。
让我们根据情况讨论这个问题：
情况一
例子给出了一种边界情况，即当 c > max(a, b) ，这种情况是不可能的 A 和 B 的电量达到 c 是的。直接输出 0。
情况二
还有一种情况我们可以直接想到，当 a = c 或者 b = c 只有一次充电操作才能完成，直接输出 1。
情况三
接下来，我们考虑一般情况，即满足以下前提：
让我们改变这个问题的想法，出的假设 a 、b、 c 必须有解决方案，所以让我们设置正确的 A 做了 x 次充(放)电，对 B 做了 y 次充(放)电，并做了 k 第三次操作。如果将 A、B 当做一大电容来看这个电容只有充放电 a 单位、充放电 b 单位这 4 种操作。那么我们就可以列出一个关系式：
由于 a、b 为非负整数，又因为前提条件 c < max(a, b) ，则 x 和 y 符号相反。
暂且，我们先不管做了几次操作三，先只考虑充放电问题，那其实就是已知 a、b、c，我们在给定范围内求解 x 和 y 的解就可以了。那么这个问题我们要如何求解呢？这就是。
扩展欧几里得算法（Extended Euclidean）
带
*的章节略有难度。如果是从解决问题的工程角度出发，可以跳过证明直接记结论。
在推导上述问题的求解算法之前，我们需要先了解以下几个概念知识。
丢番图方程（Diophantine Equation）
丢番图方程指的是：未知数个数多于方程个数，且未知数只能是整数的整数系数方程或方程组。例如以下式中，a、b、c 都为整数:
关于代数学鼻祖丢番图（Diophantus）除了有《算数》这本开山巨作之外，还有一个好玩的数学题目墓志铭，有兴趣可以自己了解。
裴蜀定理（Bézout's identity）
在数论中，裴蜀定理是一个关于最大公约数的定理。这个定理说明了对于任意整数 a、b 和他们的最大公约数 d，关于未知数 x 和 y 的线性丢番图方程：
有解，当且仅当 m 是 d 的倍数时。这个等式也被称为裴蜀等式。
裴蜀等式有解时必然有无穷多个整数解，每组解 x 、y 都称之为裴蜀数，可用辗转相除法求得。
辗转相除法实现扩展欧几里得算法
既然说可以用辗转相除法来解决这个问题，那么我们先来说明一下如何通过辗转相除法来求二元一次线性丢番图方程。
辗转相除法过程
以 23x + 17y = 1 为例，我们来求 GCD(23, 17)：
改写成余数形式
将等式右边的第一项移项：
反向带入原式
带下划线的 6 和 5 会使用 (1) 和 (2) 两个式子反向带入，形同换元：
所以反解得，x = 3, y = -4 是上述二元一次线性丢番图方程的一组解。
* 扩展欧几里得算法证明
来观察一下辗转相除法的最后两个式子，终止条件是：
当且仅当第二个式子为 0 的时候停止这个递归运算。如何延伸到一般情况呢？我们将待求变量设为字母来尝试一下。假设此时，我们要求 an 和 bn 为系数的二元一次线性丢番图方程的系数，即待求方程：
根据上述的改写余数形式，我们可以列出式一（| 是整除的意思）：
假设未到达最终的终止条件，则有：
第二个式子中我们可以发现：
同理，第 n 个式子中有：
根据辗转相除的规则，我们知道第 0 项中 b = 0、 a = 1 ，而我们要求的是第 n 项中的 a 和 b，所以可以通过 a 和 b 的递推公式逐一推导而来。
由上文证得了：
我们将其带入到第一个式子中：
所以可以求得：
由于辗转相除的推论我们可得：
所以：
即：
代码实现扩展欧几里得算法
为了实现上述的反向带入原式的过程，我们通过递归递归到最深的一层，将每一层的解带入即可完成最终的求解：
# python
def ex_gcd(a, b):
if b == 0:
return 1, 0, a
else:
x, y, r = ex_gcd(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y, r// c++
int ex_gcd(int a, int b, int &x, int &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
int r = ex_gcd(b, a % b, x, y);
int t = y;
y = x - (a / b) * y;
x = t;
return r;
}但是我们注意到，由于裴蜀定理，我们求解的丢番图方程中，等号右边的常数必须是 k * gcd(a, b)。所以我们的求解其实是：
所以通过扩展 GCD 算法求得的 x0 和 y0 这组解，并不是我们要求的最终解。同样的，我们对其扩大 k 倍就是我们想要对结果：
小结
有了这些知识，你对那道“地狱难度”的头条面试题有没有更多的想法呢？这里有一道 你可以尝试一下，做完之后想必会对扩展 GCD 算法有更深的理解。
至于头条面试题，我将在下一篇文继续讲述并代码实现此题的解法。