题目大意：求关于 \(x\) 的同余方程 $$ax \equiv 1 \pmod {b}$$ 的最小正整数解。

题解：exgcd 板子题。

代码如下

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a,b;

ll exgcd(ll a,ll b,ll &x,ll &y){

	if(!b)return x=1,y=0,a;

	ll d=exgcd(b,a%b,x,y);

	ll z=x;x=y,y=z-a/b*y;

	return d;

}

int main(){

	scanf("%lld%lld",&a,&b);

	ll x,y;

	exgcd(a,b,x,y);

	printf("%lld\n",(x%b+b)%b);

	return 0;

}