欧几里得算法即为辗转相除法
裴属定理：对于任意正整数a，b，那么一定存在整数x，y，使得ax+by=(a,b)即a和b的最大公约数（a和b能凑出来的最小的整数)扩展欧几里得算法可以求出ax+by
欧几里得算法基本原理：a，b的最大公约数==b和a%b的最大公约数
x和y的系数

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
   // return b?gcd(b,a%b):a;
   //展开写
   if(!b)//当b为0时，a和0的最大公约数为a，a*x+*y=a,x=1，y=0
   {
       x=1,y=0;
       return a;
   }
   int d= exgcd(b,a%b,y,x);//记下最大公约数 ,b都系数为y，a%b的系数为x
   //递归结束后，此时已有一组x，y，使得by+(a%b)x=d
   y-=a/b*x;
   return d;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        int x,y;//系数
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}