算法

(扩展欧几里得)

• 题目要求关于 $x$ 的同余方程 $ax \equiv c\pmod b$
• $ax \equiv c \pmod b$ 等价于 $(a * x - c) \% b = 0$，也就等价于 $a * x - c = b * y$
• 设 $y’ = -y$，则有 $a * x + b * y’ = c$
• 本题等价于计算满足方程 $a * x + b * y = c$ 的 $x$ 的最小正整数
• 普通枚举法超时
• 扩展欧几里得定理：对于给定的两个整数 $a$ 和 $b$，必存在整数 $x$ 与 $y$，使得 $a * x + b * y = \gcd(a, b)$
• 裴蜀定理：方程 $a * x + b * y = c$ （线性丢番图方程又称裴蜀等式）有整数解的充分必要条件是 $c$ 是 $\gcd(a, b)$ 的倍数
• 利用扩展欧几里得算法计算方程 $a * x + b * y = c$ 的特解

C++ 代码

#include <bits/stdc++.h>

int d, x, y;

void Extend_Gcd(int a, int b, int &d, int &x, int &y) {
    if (b == 0) {
        d = a; x = 1 / a; y = 0;
    }
    else {
        int x1, y1;
        Extend_Gcd(b, a % b, d, x1, y1);
        x = y1;
        y = x1 - a / b * y1;
    }
}

int main() {
    int a, b;
    std::cin >> a >> b;

    Extend_Gcd(a, b, d, x, y);

    std::cout << (x % b + b) % b << '\n';

    return 0;
}