AcWing 877. 扩展欧几里得算法
原题链接
简单
作者:
MeowRain
,
2024-02-18 16:18:51
,
所有人可见
,
阅读 28
#include <iostream>
using namespace std;
// 扩展欧几里得算法函数
// 参数:
// a, b: 需要计算扩展GCD的整数
// x, y: 引用参数,用于存储系数,使得 ax + by = gcd(a, b)
// 返回:
// gcd(a, b)
int ext_gcd(int a, int b, int &x, int &y) {
// 基本情况:当 b 等于 0 时,GCD 是 a,系数 x 和 y 分别为 1 和 0
if (b == 0) {
x = 1;
y = 0;
return a;
}
// 递归调用,参数交换,系数 x 和 y 交换
int d = ext_gcd(b, a % b, y, x);
// 使用公式更新 y:y = y - (a/b) * x
y -= a / b * x;
// 返回最大公约数
return d;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a, b, x, y;
cin >> a >> b;
// 调用扩展欧几里得算法函数
int gcd = ext_gcd(a, b, x, y);
// 输出方程 ax + by = gcd(a, b) 的系数 x 和 y
cout << x << " " << y << endl;
}
return 0;
}