扩展欧几里得

思路和推导

裴蜀定理

\(ax + by = c\) 有解 当且仅当 \(\gcd(a, b) | c\)。

求解 \(ax + by = \gcd(a, b)\)：

\[ \begin{aligned} ax + by = \gcd(a, b) = \gcd(b, a \bmod b)\\ bx' + (a \bmod b)y' = \gcd(b, a \bmod b)\\ bx' + (a - \left\lfloor \frac{a}{b} \right\rfloor \times b)y' = \gcd(b, a \bmod b)\\ ay' + b(x' - \left\lfloor \frac{a}{b} \right\rfloor y') = \gcd(b, a\bmod b) \end{aligned} \]

因此，我们只需要计算

\[bx' + (a \bmod b)y' = \gcd(b, a \bmod b)\]

的解，就计算出了

\[\left\{\begin{array}{l} x \gets y' \\ y \gets x' - \left\lfloor \frac{a}{b} \right\rfloor y' \end{array}\right.\]

递归的边界为：

当 \(b | a\) 时，方程为 \(ax + by = b\)，解得 \(x = 0,\: y = 1\)。

实现

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

计算同余

// P1082 [NOIP2012 提高组] 同余方程
#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int a, b, x, y;
    // 求出 a: x 在 mod b 意义下的逆元 x: x^{-1}
    scanf("%d%d", &a, &b);
    // ax + by = 1; a: x; x: x^{-1}; b: b; y: k
    exgcd(a, b, x, y);
    // ans = x (mod b)
    printf("%d", (x % b + b) % b);
    return 0;
}