Home > libalgo > 逆元

逆元

概要

$x$ と $m$ が互いに素なら $xy\%m = 1$ となる $y < m$ がただ一つ存在する．そのような $y$ を法 $m$ における $x$ の逆元といい，分数が使えるときの逆数と同じ意味なので割り算ができる．

逆元はフェルマーの小定理 ($m$ が素数のときのみ) か拡張ユークリッドの互除法を使って求めることができる．フェルマーの小定理なら $x^{m-1} = 1$ すなわち $x \times x^{m-2} = 1$ より $y = x^{m-2}$．互除法なら $xs + mt = 1$ なる $s,t$ を求めると $xs = 1 - mt = 1$ より $y = s$．

計算量

$O(\log \mathrm{MOD})$

ただし $\mathrm{MOD}$ は法．大量に呼び出す必要があり $x$ の上限が小さいときは build_modinv() で全列挙するべき．

使い方

modinv(x): $x^{-1} \mod \mathrm{MOD}$
build_modinv(n, dst): $\mathrm{MOD}$ を法とする $1, \ldots, n$ の逆元を dst を先頭とする配列に書き込む．

実装

//@require modpow.cc
//@require extgcd.cc

// フェルマーの小定理 assert(m is prime)
ll modinv(ll x) { return modpow(x, MOD - 2); }

// extgcd
// ll modinv(ll x, ll m) {
//     ll s, t;
//     extgcd(x, m, s, t);
//     return (m + s) % m;
// }

// 列挙
void build_modinv(int n, int *dst) {
    dst[1] = 1;
    for (ll i = 2; i <= n; i++) {
        dst[i] = dst[MOD % i] * (MOD - MOD / i) % MOD;
    }
}

参考文献

アルゴリズムイントロダクション
rng_2(@rng_58)/2013年03月15日 - Twilog