分析

• 同余方程$a \times x \equiv 1 \ (mod \ b)$的解x相当于是求解a的模b的乘法逆元（逆元），该方程存在解的充要条件是a、b互质。这一题是AcWing 878. 线性同余方程一个简化版，通过AcWing 878. 线性同余方程的分析也可以得出a、b必须互质才有解。

$$ a \times x \equiv 1 \ (mod \ b) \iff 存在 \ -y \in Z,\ st \ \ a \times x = b \times -y + 1 \\\\ \iff 存在 \ -y \in Z,\ st \ \ a \times x + b \times y = 1 $$

• 通过上面的转化，我们可以使用扩展欧几里得算法求解即可，假设我们得到一组解$x_0, y_0$，则所有解的通式如下（其中d=1）：

$$ \begin{cases} x = x_0 + \frac{b}{d} \times k \\\\ y = y_0 - \frac{a}{d}\times k \end{cases} \quad \quad k \in Z $$

• 我们需要求解的是最小的正整数x，关于x的通式为：$x = x_0 + b \times k$，因此最后的结果为$(x_0 \% b + b) \% b$。

代码

#include <iostream>

using namespace std;

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

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

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {

    int a, b;
    cin >> a >> b;

    int x, y;
    exgcd(a, b, x, y);

    cout << (x % b + b) % b << endl;

    return 0;
}