【正经题解】同余方程

首先对于 $ax$ ≡ $1$ ( $mod$ $b$ )； 观察数据范围可以发现 $b$ ≥ $2$ ，所以转化成 $ax$ $mod$ $b=1$
从 $mod$ 的定义中我们可以看出原方程就是 $ax-by=1$ （ $y$ 是整数）
因为一定有解，然后由裴蜀定理可以知道 $gcd$ ( $a$ , $b$ )| $1$ ，即 $gcd$ ( $a$ , $b$ ) $=1$ ，得证 $a$ , $b$ 互质。
然后就可以套扩欧模板了。

  #include<cstdio>
    using namespace std;
    typedef long long LL;
    LL a,b,x,y;
    inline void read(LL &x)
    {
        x=0; char ch=getchar();
        while (ch<'0'||ch>'9') ch=getchar();
        while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    }
    inline void exgcd(LL a,LL b,LL &x,LL &y)
    {
        if (!b) { x=1; y=0; return; }
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    int main()
    {
        read(a); read(b);
        exgcd(a,b,x,y);
        printf("%lld",(x%b+b)%b);
        return 0;
    }