扩展欧几里得算法

扩展欧几里得算法 (Extended Euclidean algorithm) 是欧几里得算法（辗转相除法）的扩展。

给定两个 非零整数 a 与 b，必存在有 整数 x 与 y，使得 $ax + by = gcd(a, b)$

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

x 与 y 的所有解：

$x' = x + \frac{b}{gcd}*K\\ y' = y - \frac{a}{gcd}*K\\ K 为任意整数$

x 的最小非负整数解：$(x \% \frac{b}{gcd} + \frac{b}{gcd}) \% \frac{b}{gcd}$（使其必然为正数）

ax + by = c 求解

可以根据上面求解的扩展欧几里来进一步的求解 $ax + by = c$（c 为任意整数）

假设 $ax + by = gcd(a, b)$ 有一组解 $(x_0, y_0)$

$ax + by = gcd(a, b)\\ 两边同乘\frac{c}{gcd}\\ a\frac{cx_0}{gcd} + b\frac{cy_0}{gcd}=c$

$ax + by = c$ 存在解的 充要条件 是 $c \% gcd == 0$，且有一组解为 $(\frac{cx_0}{gcd}, \frac{cy_0}{gcd})$

$ax + by = c$ 的全部解：

$x' = \frac{cx_0}{gcd} + \frac{b}{gcd}*K\\ y' = \frac{cy_0}{gcd} - \frac{a}{gcd}*K\\ K 为任意整数$

同余式 ax ≡​ c (mod m) 的求解

同余式：设m是给定的一个正整数，a、b是整数，若满足 $m$，则称 a 与 b 对模 m 同余，记为 $a \equiv b (mod \ m)$

• 每一整数都各自与 $[0,\ m)$ 的唯一整数同余

可以将 $ax \equiv c (mod\ m)$ 化成 $ax + by = c$

• 根据同余式定义：$(ax - c) \% m = 0$，因此存在 y 使得 $ax - c = my$ 成立，移项后令 y = -y 即可得到 $ax + by = c$

因此可以得到以下结论：

$设 a，c，m 是整数，其中 m \ge 1，则\\ 1.\ 若 cequation \% gcd(a, m) \neq 0，则同余式 ax \equiv c (mod\ m) 无解\\ 2.\ 若 c \% gcd(a, m) = 0，则同余式 ax \equiv c (mod\ m) 恰好有 gcd(a, m) 个模m意义下不同的解，且解的形式为：\\ x'=x+\frac{m}{gcd(a, m)} * K\\ 其中K = 0，1，……，gcd(a, m) - 1，x 是 ax + my = c 的一个解$