AcWing 877. 扩展欧几里得算法
给定 $n$ 对正整数 $a_i, b_i$,对于每对数,求出一组 $x_i, y_i$,使其满足 $a_i \times x_i + b_i \times y_i = gcd(a_i, b_i)$。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行,每行包含两个整数 $a_i, b_i$。
输出格式
输出共 $n$ 行,对于每组 $a_i, b_i$,求出一组满足条件的 $x_i, y_i$,每组结果占一行。
本题答案不唯一,输出任意满足条件的 $x_i, y_i$ 均可。
数据范围
$1 \le n \le 10^5$,
$1 \le a_i,b_i \le 2 \times 10^9$
输入样例:
2
4 6
8 18
输出样例:
-1 1
-2 1
题解
思路
前导题
-
利用辗转相除法求最大公约数,也就是欧几里得算法(gcd算法)
-
c++ int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
-
辗转相除法里面有一个注意点
gcd(a, b)
的下一层一定是gcd(b, a % b)
,要进行翻转,因为我们实际上是将a%b
,b
不变,a%b
的结果一定是小于b
的,如果还写成gcd(a % b, b)
,那么下一层函数会执行(a % b) % b
结果永远等于a % b
,就会导致无限递归,所以要进行翻转,将更小的a % b
放在后面。 -
- 举个例子
-
- $(78,14)=(14×5+8, 14)=(8, 14)$,在进入下一层函数时,就应写成$gcd(14, 8)$,这样才能正确执行 $14 mod 8$ 的操作
本题题意
求出一组 $x_i, y_i$,使其满足 $a_i \times x_i + b_i \times y_i = gcd(a_i, b_i)$。
前置知识
$$
裴蜀定理:
对于任意正整数a, b,一定存在整数x, y, 使得: ax + by = gcd(a, b) ,gcd(a, b)是a和b的最大公约数
$$
推导
-
我们在给
gcd()
传入参数时,将我们要求的$x, y$也传入,则第一层gcd()
就是gcd(a, b, x, y)
-
$a_i \times x_i + b_i \times y_i = gcd(a_i, b_i)$ 进入下一层
gcd()
时,变成了gcd(b, a % b)
,那么本题对应的系数$x, y$也要翻转,就变为gcd(b, a % b, y, x)
-
把
gcd(b, a % b, y, x)
的表达式根据 $a_i \times x_i + b_i \times y_i = gcd(a_i, b_i)$剖析开也就是 $b \times y + (a mod b) \times x$ -
但我们标准的$x, y$系数应该是对应的
a
和b
, $a_i \times x_i + b_i \times y_i = gcd(a_i, b_i)$也就是说这里的y
和x
相比于上一层gcd(a, b, x, y)
改变了,我们将其拆开重新去找对应于a
和b
的系数x, y
拆分 $b \times y + (a mod b) \times x$
- $a mod b = a - \lfloor\frac{a}{b}\rfloor \times b$
- 拆开
- $b \times y + (a - \lfloor\frac{a}{b}\rfloor \times b) \times x$
- $a \times x + b \times (y - \lfloor\frac{a}{b}\rfloor \times x)$
- 新的$x = x$
- 新的$y = y - \lfloor\frac{a}{b}\rfloor \times x$
x
没变,只有y
变了,只用改变y
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a, b, x, y;
int exgcd(int a, int b, int &x, int &y) //注意这里x和y一定要以引用方式传入,否则不会改变x和y本来的值,传不回solve()
{
//辗转相除,直到小括号内右边数为0
if(!b) //当b等于0找到了最大公约数a
{
//此时让系数x=1, y=0, 就能满足题目要求a*1 + b*0=gcd(a, b)=a 但往前返回的时候x和y会改变,这里的特判是为了往回递归的时候方便更新y的值
x = 1, y = 0;
return a;
}
//这里初始化d=gcd(b, a % b, y, x)的原因是要让gcd() 上一层递归返回后,都更改一次下面的系数y
int d = exgcd(b, a % b, y, x);
//重新计算系数y
y -= (a / b) * x;
return d;
}
void solve()
{
cin >> a >> b;
exgcd(a, b, x, y);
cout << x << " " << y << endl;
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
while (n -- )
{
solve();
}
return 0;
}