← all categories

Mod Basics d06d58b8

Modular exponentiation, single modular inverse (Fermat, MOD must be prime), and a linear-sieve inverse table for 1..MAXN-1 (MOD must be prime, MAXN < MOD).

Time: binpow/invMod O(\log b); invTable O(MAXN) total, O(1) per query after. tested

content/math/mod-basics.h

ll binpow(ll a, ll b, ll MOD) {
    a %= MOD;
    if (a < 0) a += MOD;
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll invMod(ll a, ll MOD) { return binpow(a, MOD - 2, MOD); }

vector<ll> invTable(int maxn, ll MOD) {
    vector<ll> inv(maxn);
    inv[1] = 1;
    for (int i = 2; i < maxn; i++) inv[i] = (MOD - MOD / i * inv[MOD % i] % MOD) % MOD;
    return inv;
}