Fifnmar edited 4 年，9 月前
欧几里得算法是求最大公约数常用的递归算法。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
根据 Bézout’s Identity, 方程
$$
ax+by=\gcd(a, b)\tag1
$$
必有整数解。
思考通过使用递归来解决这个问题。
首先，base case 是 b == 0。此时，a 就是答案，而显然 $x = 1$ 且 $y = 0$。
然后，对 recursive cases，想办法把相关式变成和 $(1)$ 同形式的方程。
由于
$$
\begin{cases}\gcd(a, b) = \gcd(b, a\;\%\;b) \a\;\%\;b = a - \frac{a}{b}\times b\end{cases}
$$
所以
$$
\begin{align}bs + (a - \frac{a}{b}\times b)t &= \gcd(a, b)\at + b(s - \frac{a}{b}\times t) &= \gcd(a, b)\end{align}
$$
对比
$$
ax + by = gcd(a, b)
$$
可以对应得出：
$$
\begin {cases}x &= t\y &= s = \frac{a}{b}\times t\g &= g\end {cases} \tag2
$$
其中 $g$ 是最大公约数。
有人喜欢把递归过程对应的变量用同样的字母表示，如 $x’$。这里，我使用了两个不同的字母表示。但对应的关系是一致的。
声明函数：
ext_gcd(a, b) -> (gcd(a, b), x, y)
where a, b, x and y are integral,
a * x + b * y = gcd(a, b);
定义如下：
auto ext_gcd(int a, int b) -> tuple<int, int, int> {
if (b == 0) {
return {a, 1, 0};
} else {
auto [g, s, t] = ext_gcd(b, a % b);
return {g, t, s - a / b * t}; // div b first, for it is modulus div.
}
}
证明：$(2)$ 式最终收敛于 $b = 0$ 的 base case。
显然，这个函数的递归式 auto [g, s, t] = ext_gcd(b, a % b); 与 gcd 相同，所以显然它和普通的 gcd 一样，都可以收敛到 $b=0$ 的情况。