P1082 [NOIP2012 提高组] 同余方程题解

· · 个人记录

置顶消息：

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

所以最后如果 $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;
}