扩展欧几里得
$gcd(a,b) = gcd(b,a\%b)$

$要求解方程ax + by = gcd(a,b)的根$

$当b = 0时 \quad ax + by = a \quad所以可以使得x = 1, y = 0$

$当b \neq 0时 \quad 因为gcd(a,b) = gcd(b, a\%b),又有$

$$bx’ + (a\%b)y’ = gcd(b,a\%b)$$

$$bx’+(a-\lfloor a/b \rfloor * b)y’ = gcd(b,a\%b)$$

$$ay’+b(x’-\lfloor a/b \rfloor y’) = gcd(b,a\%b)$$

$所以，x = y’ \quad y = x’-\lfloor a/b \rfloor y’$

#include <bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a % b, x1, y1);//计算gcd
    x = y1, y = x1 - a / b * y1;
    return gcd;
}
int main(){
    int n;
    cin >> n;
    int a,b;
    while(n--){
        cin >> a >> b;
        int x, y;
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}