int.mod.pow

整数 \(a, n\)\(m\) について \[a^n \bmod m\]\(O(\log n)\) で求める.

NOTE 特に \(m\) が素数の時, \(a^{m-2}\)\(a^{-1}\) になる (フェルマーの小定理).

int.mod.pow.rs

fn powmod
    <K: Copy + std::ops::Mul<Output=K> + std::ops::Div<Output=K> + std::ops::Rem<Output=K>>
    (a: K, n: u64, m: K) -> K {
    if n == 0 {
        a / a
    } else if n == 1 {
        a % m
    } else {
        let y = powmod((a * a) % m, n / 2, m);
        if n % 2 == 0 {
            y
        } else {
            (y * a) % m
        }
    }
}