引入一个定理：Bezout定理

对于任意整数 $a,b$ 存在一对整数$x,y$,满足$ax+by=gcd(a,b)$

证明：

在欧几里得算法的最后一步，即$b=0$时，显然有一对整数，$x=1,y=0$ ,满足$ax+by=a*1+b*0=gcd(a,0)$

若$B>0$ 则$gcd(a,b)=gcd(b,a mod b)$.

假设存在一对整数$x,y$,满足$b*x+(a mod b) * y=gcd(b,a mod b)$ ,因为$b*x+(a mod b)*y=b*x+(a-(a/b)*b)*y=a*y+b*(x+(a/b)*y)$ 所以令$x'=y,y'=(x+(a/b)*y)$

此时的$x',y'$便满足$a*x'+b*y'=gcd（a,b）$ 逆推即可得到一组特解

将$a$ 变成最小正整数便得出答案

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll a,b,x,y;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0){
		x=1,y=0;
		return a;
	} 
	ll ans=exgcd(b,a%b,x,y);
	ll z=x;
	x=y;
	y=(z-y*(a/b));
	return ans;
	
} 
int main()
{
	scanf("%d%d",&a,&b);
	exgcd(a,b,x,y);
	cout<<(x % b + b) % b;
 }