扩展欧几里得定理(exgcd)

P1082 [NOIP2012 提高组] 同余方程

P5656 【模板】二元一次不定方程 (exgcd)

#include<cstdio>

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

int a, b, d, x, y;
int main() {
    scanf("%d %d", &a, &b);
    d = exgcd(a, b, x, y);
    x *= d;
    x = (x % b + b) % b;
    printf("%d\n", x);
}