先看题目：https://ac.nowcoder.com/acm/problem/16563
解题思路：
exgcd模板题，求ax≡1(mod b)，可以写为方程的形式 ax = yb + 1, 即 ax - by = 1，这个符号可以塞到y里，令k=-y，就还是二元线性方程的形式了 —— ax + bk = 1
exgcd可以解决ax+by = (a,b),那么x/(a,b), y/(a,b) 就是ax+by = 1的解。我们知道通解为x=x0+kb1,y=y0+k*a1,(b1 = b/(a,b), a1 = a/(a,b))，要求ax+by=1，x的最小正整数解，再写个while循环枚举k就搞定了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd_ex(ll a, ll b, ll &x, ll &y)
{
    if(b == 0) {x = 1; y = 0; return a;}
    ll d = gcd_ex(b, a%b, y, x);
    y = y - a/b * x;
    return d;
}
int main()
{
    ll a, b;
    ll x, y;
    cin >> a >> b;
    ll m = gcd_ex(a, b, x, y);
    ll ans = x/m;
    while(ans <= 0) {
        ans+=(b/m);
    }
    cout << ans << endl;
}