扩展欧几里得算法如何应用于求解？
摘要：66.Acwing基础课第877题-简单-扩展欧几里得算法 题目描述 (给定 n 对正整数 a_i,b_i，对于每对数，求出一组 x_i,y_i，使其满足 a_i×x_i+b_i&
66.Acwing基础课第877题-简单-扩展欧几里得算法
题目描述
\(给定 n 对正整数 a_i,b_i，对于每对数，求出一组 x_i,y_i，使其满足 a_i×x_i+b_i×y_i=gcd(a_i,b_i)\)。
输入格式
\(第一行包含整数 n\)。
\(接下来 n 行，每行包含三个整数 a_i,p_i\)。
输出格式
\(输出共 n 行，对于每组 a_i,b_i，求出一组满足条件的 x_i,y_i，每组结果占一行\)。
\(本题答案不唯一，输出任意满足条件的 x_i,y_i 均可\)。
数据范围
\(1≤n≤10^5\),
\(1≤a_i,b_i≤2×10^9\)
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1
代码：
// 包含输入输出流头文件（cin/cout依赖，本代码用C风格IO，保留作为通用模板）
#include <iostream>
#include <algorithm>
using namespace std;
// 扩展欧几里得算法核心函数
// 功能：求解 ax + by = gcd(a, b) 的一组整数解 (x, y)，并返回gcd(a, b)
// 参数说明：
// a, b：方程的系数
// x, y：引用传递，用于存储求得的一组解
// 返回值：d = gcd(a, b)（a和b的最大公约数）
int exgcd(int a, int b, int &x, int &y)
{
// 递归边界：当b=0时，方程变为 a*1 + 0*0 = a，即gcd(a,0)=a
if (!b)
{
x = 1, y = 0; // 此时特解为x=1，y=0
return a; // 返回最大公约数a
}
// 递归调用：欧几里得算法的核心（gcd(a,b)=gcd(b,a%b)）
// 注意：递归时交换了x和y的位置，是为了后续推导方便
int d = exgcd(b, a % b, y, x);
// 回溯推导解：从递归边界反向计算当前层的x,y
// 推导依据：
// 假设递归得到 b*x' + (a%b)*y' = d
// 而 a%b = a - (a/b)*b（a/b是整数除法）
// 代入得：b*x' + (a - (a/b)*b)*y' = d → a*y' + b*(x' - (a/b)*y') = d
// 对比 ax + by = d，可得：x = y', y = x' - (a/b)*y'
// 由于递归时已经交换了x和y（当前x是原来的y'，当前y是原来的x'）
// 因此简化为：y -= a/b * x
y -= a / b * x;
return d; // 返回最大公约数
}
int main()
{
int n; // n：测试用例的组数
// C风格输入：比cin更快，适合竞赛大数据量场景
scanf("%d", &n);
// 循环处理n组测试用例
while (n -- )
{
int a, b; // a, b：需要求解 ax + by = gcd(a,b) 的系数
scanf("%d%d", &a, &b);
int x, y; // 存储方程的一组解
exgcd(a, b, x, y); // 调用扩展欧几里得算法求解
// 输出求得的一组特解x和y
printf("%d %d\n", x, y);
}
return 0; // 程序正常结束
}