(另类的扩展欧几里得)

直接上代码了（纯属学术交流，不建议实战）

#include<bits/stdc++.h>
using namespace std;

int n,a,b,x,y;

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1; y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int tmp=y;
    y=x-a/b*y;
    x=tmp;
    return d;
}

int main(){
    cin>>n;
    while(n--){
        x=y=0;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}