欧几里得算法

欧几里得算法

用于求解两个数 \(a,b\) 的最大公约数，\(\gcd(a,b) = \gcd(b,a \bmod b)\)，为了方便证明，我们约定 \(a > b\)，证明：

设 \(r = a \bmod b = a - k \cdot b\)，\(d \mid a\) 且 \(d \mid b\)，显然 \(a = k \cdot b + r\)，那么 \(\frac{r}{d} = \frac{a}{d} - \frac{k \cdot b}{d}\)，因为 \(\frac{a}{d} - \frac{k \cdot b}{d}\) 显然为整数，所以 \(\frac{r}{d}\) 也为整数，所以可证 \(\gcd(a,b) = \gcd(b,a \bmod b)\)。\(\Box\)

所以我们就可以写出如下代码：

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

因为每次进行取模再递归，所以时间复杂度为 \(\mathcal{O(\log a)}\)。

扩展欧几里得算法

用于求 \(ax + by = \gcd(a,b)\) 的一组可行解。

前置知识：裴蜀定理：对于任意整数 \(a,b\)，存在一对整数 \(x,y\)，满足 \(ax+by=\gcd(a,b)\)。

推导：

由欧几里得算法，可得 \(ax_1 + by_1 = \gcd(a,b)\) 等同于 \(bx_2 + (a \bmod b)y_2 = \gcd(b,a \bmod b)\)。

所以 \(ax_1 + by_1 = bx_2 + (a \bmod b)y_2\)，将 \(a \bmod b\) 转换，得到 \(ax_1 + by_1 = bx_2 + (a - \left \lfloor \frac{a}{b} \right \rfloor \cdot b)y_2\)。

把式子拆开 \(ax_1 + by_1 = bx_2 + ay_2 - \left \lfloor \frac{a}{b} \right \rfloor \cdot b \cdot y_2\)，

合并 \(ax_1 + by_1 = ay_2 + b \cdot (x_2 - \left \lfloor \frac{a}{b} \right \rfloor \cdot y_2)\)，

得到 \(x_1 = y_2,y_1 = (x_2 - \left \lfloor \frac{a}{b} \right \rfloor \cdot y_2)\)，那么我们就可以根据这个，不断递归求解，当递归到 \(b = 0\) 时，返回 \(a\) 的值即可，为了方便操作，可以将 \(x,y\) 取地址。

可以写出如下代码：

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

一般的，对于 \(ax + by = c\)，我们可以知道，该方程有整数解当且仅当 \(\gcd(a,b) \mid c\)。

此时我们可以优先求解 \(ax' + by' = \gcd(a,b)\)，令 \(d = \gcd(a,b)\)，我们可以得到方程的通解为