[C++][算法基础]扩展欧几里得算法

给定 𝑛 对正整数 𝑎𝑖,𝑏𝑖，对于每对数，求出一组 𝑥𝑖,𝑦𝑖，使其满足 𝑎𝑖×𝑥𝑖+𝑏𝑖×𝑦𝑖=𝑔𝑐𝑑(𝑎𝑖,𝑏𝑖)。

输入格式

第一行包含整数 𝑛。

接下来 𝑛 行，每行包含两个整数 𝑎𝑖,𝑏𝑖。

输出格式

输出共 𝑛 行，对于每组 𝑎𝑖,𝑏𝑖，求出一组满足条件的 𝑥𝑖,𝑦𝑖，每组结果占一行。

本题答案不唯一，输出任意满足条件的 𝑥𝑖,𝑦𝑖 均可。

数据范围

1≤n≤,
1≤ai,bi≤2×

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

代码：

#include<iostream>
#include<algorithm>
using namespace std;

int n;

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

int main(){
    cin>>n;
    while(n--){
        int a,b,x,y;
        cin>>a>>b;
        int d = EXT_gcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}