[luoguP1082] 同余方程（扩展欧几里得）

传送门

ax≡1(mod b)

这个式子就是 a * x % b == 1 % b

相当于 a * x - b * y == 1

只有当 gcd(a,b) == 1 时才有解，也就是说 ax + by = c 有解的充要条件是 c % gcd(a,b) == 0

一般，我们能够找到无数组解满足条件，但是一般是让你求解出最小的那个正整数解

即为 (x % b + b) % b)，+b是为了保证不为负数

可以这样想 a * x % b == 1 % b

　　　  -> a * x % b == 1

　　　  -> (a * x % b) % b == 1

求 x 最小正整数，那么直接取膜就好。

——代码

#include <cstdio>

int a, b, x, y, gcd;

inline int exgcd(int a, int b, int &x, int &y)
{
    if(!b){x = 1, y = 0; return a;}
    int r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
}

int main()
{
    scanf("%d %d", &a, &b);
    gcd = exgcd(a, b, x, y);
    printf("%d", (x % b + b) % b);
    return 0;
}