Modular Arithmetic

Why problems ask for a remainder

When a problem says “print the answer modulo 1000000007”, it is telling you the true answer is astronomically large — often larger than any fixed-width integer can hold. Rather than asking for big-integer arithmetic, the problem asks for the remainder, which stays small.

That constant, 10⁹+7, is prime and just under 2³⁰. Both properties matter: primality makes division possible, and the size means two values below it multiply to under 2⁶⁰, which fits in a long.

static final long MOD = 1_000_000_007L;

The rules that hold

Addition, subtraction, and multiplication all commute with taking the remainder. You can reduce at every step and the final answer is unchanged.

long add(long a, long b) { return (a + b) % MOD; }
long mul(long a, long b) { return (a * b) % MOD; }

Subtraction needs care because Java’s % can return a negative value.

long sub(long a, long b) { return ((a - b) % MOD + MOD) % MOD; }

Adding MOD before the second reduction forces the result non-negative. Skipping this produces a negative answer that looks almost right, which is a hard bug to spot.

// WRONG — overflows long long before the modulo
long product = 1;
for (int i = 1; i <= n; i++) product *= i;
System.out.println(product % MOD);

// CORRECT — stays below MOD^2 at every step
long product = 1;
for (int i = 1; i <= n; i++) product = product * i % MOD;

Fast exponentiation

Computing a^b mod m by multiplying b times is O(b), which is hopeless when b is 10¹⁸. Repeated squaring does it in O(log b).

The idea: a^b is (a^(b/2))^2 when b is even, and a · a^(b-1) when odd. Reading the exponent’s bits from the bottom turns that into a loop.

static long power(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Each iteration halves the exponent, so 10¹⁸ takes about 60 steps.

Division and modular inverses

You cannot divide directly under a modulus. (a / b) % m is not ((a % m) / (b % m)) % m — integer division discards information the remainder no longer carries.

Instead multiply by the modular inverse of b: the value b⁻¹ such that b · b⁻¹ ≡ 1 (mod m).

When m is prime and b is not a multiple of it, Fermat’s little theorem gives the inverse directly:

static long inverse(long b, long mod) {
    return power(b, mod - 2, mod);        // requires mod to be prime
}

static long divide(long a, long b, long mod) {
    return a % mod * inverse(b, mod) % mod;
}

Each inverse costs O(log m). If you need many inverses of consecutive small numbers, precompute them in one linear pass rather than calling power repeatedly.

Factorials and binomial coefficients

Counting problems usually need “n choose k” modulo a prime. Precompute factorials and their inverses once, then each coefficient is O(1).

static final int MAXN = 1_000_001;
static long[] fact = new long[MAXN];
static long[] invFact = new long[MAXN];

static void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    // one inverse, then walk downwards
    invFact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 1; i > 0; i--) {
        invFact[i - 1] = invFact[i] * i % MOD;
    }
}

static long choose(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

Computing the largest inverse factorial once and stepping downward avoids calling power a million times — the whole precomputation is O(N + log MOD).

The if (k < 0 || k > n) return 0; guard matters. Many recurrences naturally produce out-of-range arguments, and returning 0 for them is both mathematically right and simpler than avoiding them.

Operations under a prime modulus

Related