拓展欧几里得算法

前置知识：欧几里得算法

欧几里得算法，是一个可以在 $O(\log \min(a, b))$ 的时间内求出 $\gcd(a, b)$ 的算法。

而拓展欧几里得算法不仅可以在 $O(\log \min(a, b))$ 的时间内求出 $\gcd(a, b)$，还可以求出一个二元一次不定方程 $ax + by = \gcd(a, b)$ 的一组解。

首先，我们来回顾一下欧几里得算法。

回顾

首先，$\gcd(a, b) = \gcd(a - b, b)$，因为 $\gcd(a, b) | a$ 且 $\gcd(a, b) | b$。

然后，$\gcd(a, b) = \gcd(b, a \bmod b)$，因为 $a \bmod b = a - b\left\lfloor\dfrac{a}{b}\right\rfloor$。

所以，$\gcd(a, b)$ 的值可以通过递归调用 $\gcd(b, a \bmod b)$ 直到 $a, b$ 至少有一个为 $0$。

因为 $a \bmod b < \min(\dfrac{a}{2}, b)$，所以至多会调用 $\log \min(a, b)$ 次。

我们可以类比欧几里得算法，定义 $\operatorname{exgcd}(a, b)$ 为返回 $x, y, \gcd(a, b)$ 三个值的函数。

它的算法流程是这样的：

1. 如果 $b = 0$，返回 $x = 1, y = 0, \gcd(a, b) = a$。
2. 设 $a' = b, b' = a \bmod b$，递归调用 $\operatorname{exgcd}(a', b')$ 求出 $x', y', \gcd(a', b')$，其中 $x', y'$ 为 $a'x' + b'y' = \gcd(a', b')$ 的一组解。
3. 令 $x = y', y = x' - y'\left\lfloor\dfrac{a}{b}\right\rfloor$，返回 $x, y, \gcd(a', b')$。

时间复杂度和欧几里得算法一样，是 $O(\log \min(a, b))$。

为什么这样是对的呢？

证明

根据之前的结论，$\gcd(a', b') = \gcd(a, b)$。

又因为 $ax + by = \gcd(a, b)$ 且 $a'x' + b'y' = \gcd(a', b')$，所以 $ax + by = a'x' + b'y' \ (1)$。

将 $a, b$ 代入 $a', b'$ 得 $a' = b, b' = a \bmod b = a - b\left\lfloor\dfrac{a}{b}\right\rfloor$。

再将 $a', b'$ 代入 $(1)$，得：

$\begin{aligned} ax + by & = bx' + (a - b\left\lfloor\dfrac{a}{b}\right\rfloor)y'\\ ax + by & = bx' + ay' - b\left\lfloor\dfrac{a}{b}\right\rfloor y'\\ ax + by + b\left\lfloor\dfrac{a}{b}\right\rfloor y' & = bx' + ay'\\ ax + b(y + \left\lfloor\dfrac{a}{b}\right\rfloor y') & = ay' + bx'\\ \end{aligned}$

所以，有：

$\begin{aligned} x & = y'\\ y + \left\lfloor\dfrac{a}{b}\right\rfloor y' & = x'\\ y & = x' - \left\lfloor\dfrac{a}{b}\right\rfloor y'\\ \end{aligned}$

至此，算法正确性得证。

代码实现：

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