理解扩展欧几里得算法

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;

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 t = x;//下一步回溯回来的x；
    x = y;//这一步的x应该等于y；
    y = t - a/b*y;//这一步的Y
    return d;
}
int main(){
    int n;
    cin>>n;
    int a,m,b;
    for (int i = 0; i < n; i ++ ){
        cin>>a>>b>>m;
        int x,y;
        int d = exgcd(a,m,x,y);
        if(b%d){
            puts("impossible");
        }else{
            cout<<(LL)x*b/d%m<<endl;
        }

    }
}