本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-19 10:41:29

置顶消息：

zgc大佬认为本题解的 $x = (x \mod b + b) \mod b$ 是错的，看来本题解应该是出错了，但是我太弱了不会改，这篇题解很垃圾

难度：$\color{green}\text{普及+/提高}$

题目分析：

题目要求关于 $x$ 的方程 $ax \equiv 1(\mod b)$ ，也就是 $ax \mod b = 1$ 的最小整数解。
可以发现，$x$ 就是 $a$的逆元，记作 $inv(a)$， 然后方程转换为：
$a \times inv(a) + b \times y = 1$
这么转化的原因是 $a \times inv(a)$ 与 $1$ 之间的差肯定是 $b$ 的倍数。（$y$ 代表 $b$ 的多少倍，可以为负数）
转化完之后就可以直接用扩欧求解了。
最后答案可能不是最小，也可能是负数。
先上一个式子:
若 $ax \mod b = 1$,
那么 $a(x+bn) \mod b = 1$
$n$ 是一个变量。
所以最后如果 $x$ 是负数，就大量加上 $b$ 变为正数，如果太大就大量减去 $b$ 即可。
最后处理的式子： $x = (x \mod b + b) \mod b$
注解：$x \mod b + b$处理负数，最后括号外面的 $\mod b$ 处理正数。

代码：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll x,y;
void exgcd(ll a,ll b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    ll tmp=x;
    x=y;
    y=tmp-a\/b*y;
}
int main()
{
    scanf("%lld%lld",&a,&b);
    exgcd(a,b);
    printf("%lld",(x%b+b)%b);
    return 0;
}