C++ 代码

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


//exgcd是在gcd代码的基础上进行改进的
int exgcd(int a,  int  b, int &x, int &y)
{
    if(!b)
    {
        //b=0时 gcd(a,b) = a, a*x+b*y = gcd(a,b) = a ---> x=1, y=0;
        x = 1, y = 0;
        return 1;
    }
    //交换y，x的位置是进行回溯，倒推出最初的x，y
    int d = exgcd(b, a%b, y, x);
    y -= a/b*x;

    return 1;

}
int main()
{
    int n, x, y;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >>a >> b;
        exgcd(a, b, x, y);

        cout << x << " " << y << endl;
    }


    return 0;
}