#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
return;
}
exgcd(b,a%b,x,y);
ll tmp=x;
x=y,y=tmp-(a/b)*y;
}
int main(){
ll a,b;
scanf("%lld%lld",&a,&b);
ll x,y;
exgcd(a,b,x,y);
printf("%lld\n",(x+b)%b);
return 0;
}
原文：https://www.cnblogs.com/zbsy-wwx/p/11834570.html