JZTXT

扩展欧几里得算法

发布时间 2023-04-07 21:13:09作者: 2huk

扩展欧几里得算法

题目描述

给定 \(a\) 和 \(b\)，求出一组 \(x\) 和 \(y\)，使得 \(a \cdot x + b \cdot y = \gcd(a, b)\)。

样例输入输出

8 18

-2 1

\(8 \times (-2) + 18 \times 1 = \gcd(8, 18) = 2\)

欧几里得算法

欧几里得算法适用于求两个数的最大公约数。

int Euclid_gcd(int a, int b){
	if(!b){
		return a;
	}
	return gcd(b, a%b);
}

分析

如果要解决最上方的问题，可以在欧几里得算法上进行补充。但函数的返回值仍然为 \(\gcd(a, b\)，只是在求最大公约数的过程中将 \(x\) 和 \(y\) 求解出来。

由于要求解 \(x\) 和 \(y\)，函数可以长成这样：

int Expand_Euclid_gcd(int a, int b, int &x, int &y);

其中的 &x 和 &y 是传引用，即函数内部的两个数值如果发生变化会影响到主函数中同样的 \(x\) 和 \(y\)。

边界

对于朴素欧几里得算法，如果 \(b=0\)，那么返回 \(a\)。如果对于扩展欧几里得算法，\(b=0\) 时，不难推出 \(x=1,y=0\)。

将 \(0\) 替换掉 \(a \cdot x + b \cdot y = \gcd(a, b)\) 里的 \(b\)，得：

\[a \cdot x + 0 \cdot y = \gcd(a, 0) \]

其中 \(\gcd(a, 0) = a\)，因此还可以化简：

\[a \cdot x + 0 \cdot y = a \]

对于这个式子，可以直接对 \(x\) 和 \(y\) 进行求解，即 \(x = 1\)，\(y = 任意数\)，这里规定 \(y = 0\)，方便以后数据的计算。

因此，代码就有：

if(!b){
	x = 1, y = 0;
	return a;
}

求模

抛开问题，首先我们讨论求模的另类形式。

我们知道，\(a \bmod b\) 的值是 \(a\) 除以 \(b\) 产生的余数，那么显然就有

\[a \div b = \left \lfloor \dfrac{a}{b} \right \rfloor \cdots\cdots a \bmod b \]

将其变形：

\[a - b \cdot \left \lfloor \dfrac{a}{b}\right \rfloor = a \bmod b \]

求解

求解最终的 \(x\) 和 \(y\)，首先将它们的最大公约数求出来，即

int d = Expand_Euclid_gcd(b, a%b, y, x);

我们定义 \(d\) 来存储两个数的最大公约数。

关于为什么要把 \(x\) 和 \(y\) 的位置颠倒，是因为这样更加统一，因为颠倒后原始就相当于变成了如下形式，其中的 \(b\) 和 \(y\) 还是连在一起的。

\[原式 = a \cdot x + b \cdot y = \gcd(a, b)\\ 递归 = b \cdot y + x \cdot (a \bmod b) = d \]

而我们又可以把 \(a \bmod b\) 换成 \(a - b \cdot \left \lfloor \dfrac{a}{b}\right \rfloor\)，因此上式变形为：

\[b \cdot y + x \cdot\left(a - b \cdot \left \lfloor \dfrac{a}{b} \right \rfloor \right) = d \]

上式整理可得：

\[a \cdot x + b \cdot \left( y - \left \lfloor \dfrac{a}{b} \right \rfloor \cdot x \right) = d \]

再把 \(a\) 和 \(b\) 的系数分别提出来，得到：

\[a \cdot x + b \cdot \left( y - \left \lfloor \dfrac{a}{b} \right \rfloor \cdot x \right) = d \]

至此，这个式子与前面的原式几乎一样，不同的是原来的 \(y\) 变成了现在的 \(y - \left \lfloor \dfrac{a}{b} \right \rfloor \cdot x\)，等式的值没有发生变化。

也就是说，如果要得到正确答案，\(y\) 要在本身的基础上减 \(\left \lfloor \dfrac{a}{b} \right \rfloor \cdot x\)，代码为：

y -= a / b * x;		// 整数相除自动下取整

函数的最后返回 \(d\)。

扩展欧几里得算法代码

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