扩展欧几里得算法：

裴蜀定理：

对于a,b总是存在非零整数x,y使得 ax + by = (a , b)
证明：
因为a,b两者的最大公约数是(a,b)=d的，所以ax+by的最大公约数也是d，所以会存在x,y使得两者相等

代码：

#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else{

        int d= exgcd(b,a%b,y,x);  //注意这里****
         y=y-a/b*x;              //*************,X,y这样的变换关系只进行一次，所以
                                 //不可以写为y=y-a/b*x; 
                                 //     return exgcd(b,a%b,y,x);
        return d;
    }
}
int main(){
    int n;
    cin>>n;
    int x,y,a,b;
    while(n--){
        cin>>a>>b;
        int c=exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }

    return 0;
}