ホーム > libalgo

逆元

概要

$x$ と $m$ が互いに素なら $xy\%m = 1$ となる $y < m$ がただ一つ存在する. そのような $y$ を $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$.

大量に呼び出す必要があり $x$ の上限が小さいときは buildModInv() で全列挙するべき.

計算量

$O(\log m)$

使い方

modpow(x,y,m)
$x^y \mod m$
buildModInv(m = 1000000007)
$m$ を 法とする逆元を $1\,000\,000$ 個列挙する

実装

拡張ユークリッドの互除法

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

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

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

// 列挙
template <ll mod = 1000000007>
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;
    }
}

参考文献