간단한 exgcd

1. exgcd

tuple<ll, ll, ll> extendedGCD(ll a, ll b) { // ax + by = gcd(a, b)
    if (b == 0) return {1, 0, a};
    auto [x2, y2, g] = extendedGCD(b, a % b);
    return {y2, x2 - (a / b) * y2, g};
}

베주항등식 $ax_1 + by_1 = g$ 는 항상 해 존재
$let)~ a=bk+r$
$(bk + r)x_1 + by_1 = g$
$b(kx_1+y_1) + rx_1 = g$
$let)~ x_2 = kx_1+y_1, y_2=x_1$
$\therefore x_1=y_2, y_1 = x_2-ky_2$

2. modular inverse

ll modInverse(ll a, ll b) { // a^-1 mod b
    auto [x, y, g] = extendedGCD(a, b); //ax + by = g
    if (g == 1) return (x + b) % b;
    return -1;
}

3. $n$이하 모든 자연수의 $mod$에 대한 역원 계산 $O(N + log(mod))$

vector<ll> fac(n + 1, 1);
for (int i = 2; i < fac.size(); i++) fac[i] = fac[i - 1] * i % mod;
vector<ll> facInv(fac.size(), modInverse(fac.back(), mod));
for (int i = facInv.size() - 1; i > 0; i--) facInv[i - 1] = facInv[i] * i % mod;
vector<ll> inv(n + 1, 1);
for (int i = 2; i < inv.size(); i++) inv[i] = facInv[i] * fac[i - 1] % mod;

4. $n$이하 모든 자연수의 소수 $mod$에 대한 역원 계산 $O(N)$

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

$p = \left\lfloor \dfrac{p}{n} \right\rfloor n + p \% n$
$-\left\lfloor \dfrac{p}{n} \right\rfloor n \equiv p \% n \pmod{p}$
$n^{-1} \equiv -\left\lfloor \dfrac{p}{n} \right\rfloor (p \% n)^{-1} \pmod{p}$

 

p가 소수라면 모든 p%n이 0이 아님이 보장되므로 $(p \% n)^{-1}$ 존재

$\because \forall n \in \mathbb{Z}, 2 \le n < p \implies n \nmid p$