求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll x,y,a,b;
void exgcd(ll a, ll b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }
    exgcd(b,a%b);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return ;
}
int main()
{
    ll a,b;
    while(cin>>a>>b)
    {
        exgcd(a,b);
        cout<<(x+b)%b<<endl;
    }
}