扩展欧几里得算法

欧几里得算法

欧几里得算法又称为辗转相除法，是用来计算两个非负整数a,b的最大公约数的。

实现方式也非常简单

C++

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

扩展欧几里得算法

顾名思义，扩展欧几里得算法就是欧几里得算法的扩展版

扩展欧几里得算法是用来解决一个很简单的问题。

对于一对正整数a, b求出一组x, y满足
a i ∗ x i + b i ∗ y i = g c d ( a i , b i ) a_i * x_i + b_i * y_i = gcd(a_i,b_i) ai​∗xi​+bi​∗yi​=gcd(ai​,bi​)
简单理解就是用x个a和y个b组出它们的最大公约数，其中x或y是负数。

求解这个问题是一个很简单的思路，首先求最大公约数我们会使用欧几里得算法（还有一种方法是更相减损术），在我们使用欧几里得算法求解的时候可以在每一层求解的过程中记录一下用了多少个a和b，当求出最大公约数的时候也就求出了所求的结果。

先给出代码，然后再进行讲解

C++

#include 

using namespace std;

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

int main()
{
	int n;
	cin >> n;
	int a, b, x, y;
	while (n--)
	{
		cin >> a >> b;
		exgcd(a, b, x, y);
		cout << x << ' ' << y << endl;
	}
	return 0;
}

首先这个问题要求解两个值，所以我们要递归引用两个值。

当我们运行过后第13行的函数后，所得到的x与y是满足

令d = gcd(a, b)
b ∗ y + ( a % b ) ∗ x = d b*y + (a\%b)*x = d b∗y+(a%b)∗x=d
将这个式子进行数学代换可得
b ∗ y + ( a − ⌊ a b ⌋ ∗ b ) ∗ x = d b*y + (a - \lfloor \frac{a}{b} \rfloor*b)*x = d b∗y+(a−⌊ba​⌋∗b)∗x=d

a ∗ x + b ∗ ( y − ⌊ a b ⌋ ∗ b ) = d a*x + b*(y - \lfloor \frac{a}{b} \rfloor * b) = d a∗x+b∗(y−⌊ba​⌋∗b)=d

而当前这一层函数中的状态是
a ∗ x + b ∗ y     ! =     d a*x + b*y \ \ \ {!= }\ \ \ d a∗x+b∗y   !=   d
只需要将y减去a/b*x即可使当前这一层函数满足结果

扩展欧几里得算法的应用

P1082 NOIP2012 提高组 同余方程

求 关 于 X 的 同 余 方 程  ax≡1(mod b)  的 最 小 正 整 数 解 。

求关于X的同余方程 \verb| ax≡1(mod b) |的最小正整数解。

求关于X的同余方程 ax≡1(mod b) 的最小正整数解。

原式可以转换为ax + by = 1

求出x将其转换为正数即可