考虑扩展欧几里得定理求逆元。

可得 $b\vert ax-1$，因为 $ax\mod b=1$。

所以我们将 $ax\equiv1(\mod b)$ 转化为 $ax-bk=1$。

直接套板子，但是注意到 $x$ 可能是负数所以需累加转为正整数。

#include<bits/stdc++.h>
using namespace std;

int a,b,x,y;
//拓展欧几里得
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int res=exgcd(b,a%b,x,y);
	int temp=x; 
	x=y;
	y=temp-a/b*y;
	return res; 
} 
int main(){
	cin>>a>>b;
	exgcd(a,b,x,y);
	cout<<(x+b)%b;
	return 0;
}