GCD与EXGCD

GCD 与 EXGCD

核心等式： $g cd (a, b) = g cd (b, a mod b)$ ，当 $b = 0$ 时返回 $a$ 。

int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}

求 $a x + b y = g cd (a, b)$ 的一组整数解。

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

解满足 $∣ x ∣ \leq b, ∣ y ∣ \leq a$ 。

当 $g cd (a, m) = 1$ 时， $a$ 在模 $m$ 下存在逆元。

方法一：费马小定理（ $m$ 为素数）： $a^{- 1} \equiv a^{p - 2} (mod p)$ 。

方法二：EXGCD：求解 $a x \equiv 1 (mod m)$ 。

方法三：线性递推（ $p$ 为素数，预处理 $1 \sim n$ 逆元）：

vector<int> inv(n + 1);
inv[1] = 1;
for (int i = 2; i <= n; ++i)
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;

方法四：批量逆元（ $O (n + lo g m)$ ）：预处理前缀积 $S_{i}$ ，求 $S_{n}^{- 1}$ 后回推。