Modular Arithmetic

In Competitive Programming, problems often have very large answers, requiring results as “mod $10^9 + 7$” or other values.

Basic Modulo

Modulo operation finds the remainder after division.

$a \mod m = r$ means $a = qm + r$ where $0 \leq r < m$

const int MOD = 1e9 + 7;

int mod(int x) {
    return ((x % MOD) + MOD) % MOD;
}

⚠️ Important: In C++, modulo of negative numbers may give negative results. e.g., -7 % 5 = -2. Add MOD back to fix this.

Properties of Modular Arithmetic

Addition and Subtraction

$(a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m$ $(a - b) \mod m = ((a \mod m) - (b \mod m) + m) \mod m$

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

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

Multiplication

$(a \times b) \mod m = ((a \mod m) \times (b \mod m)) \mod m$

long long mulMod(long long a, long long b) {
    return ((a % MOD) * (b % MOD)) % MOD;
}

Division (Requires Modular Inverse)

$\frac{a}{b} \mod m = (a \times b^{-1}) \mod m$

Where $b^{-1}$ is the modular inverse of $b$

Modular Exponentiation

Efficient modular exponentiation.

Binary Exponentiation

Calculate $a^n \mod m$ in $O(\log n)$

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

Principle

• If $n = 0$: result = $1$
• If $n$ is even: $a^n = (a^{n/2})^2$
• If $n$ is odd: $a^n = a \times a^{n-1}$

Example: $2^{10}$

• $2^{10} = (2^5)^2$
• $2^5 = 2 \times (2^2)^2$
• $2^2 = (2^1)^2$
• $2^1 = 2 \times 2^0 = 2$

Modular Inverse

$b^{-1}$ is the number such that $b \times b^{-1} \equiv 1 \pmod{m}$

Method 1: Fermat’s Little Theorem

If $m$ is prime:

$b^{-1} \equiv b^{m-2} \pmod{m}$

long long modInverse(long long b, long long mod = MOD) {
    return power(b, mod - 2, mod);
}

// Division a / b mod m
long long divMod(long long a, long long b) {
    return mulMod(a, modInverse(b));
}

Method 2: Extended Euclidean Algorithm

Works for general $m$ where $\gcd(b, m) = 1$

long long extGcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long modInverseExt(long long b, long long mod = MOD) {
    long long x, y;
    extGcd(b, mod, x, y);
    return (x % mod + mod) % mod;
}

Method 3: Pre-compute Inverse from 1 to n

const int MAXN = 1e6 + 5;
long long inv[MAXN];

void precomputeInverse(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
    }
}

Factorial and Combinations

Pre-compute Factorial

const int MAXN = 1e6 + 5;
long long fact[MAXN], invFact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    
    invFact[MAXN-1] = modInverse(fact[MAXN-1]);
    for (int i = MAXN-2; i >= 0; i--) {
        invFact[i] = (invFact[i+1] * (i+1)) % MOD;
    }
}

Binomial Coefficient (nCr)

$\binom{n}{r} = \frac{n!}{r!(n-r)!}$

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

Lucas’ Theorem

For computing $\binom{n}{r} \mod p$ when $n$ is very large and $p$ is prime

$\binom{n}{r} \equiv \prod_{i=0}^{k} \binom{n_i}{r_i} \pmod{p}$

Where $n = \sum_{i} n_i p^i$ and $r = \sum_{i} r_i p^i$

long long lucas(long long n, long long r, long long p) {
    if (r == 0) return 1;
    return (lucas(n / p, r / p, p) * nCr(n % p, r % p)) % p;
}

Usage Examples

Problem: Find $2^{1000000000} \mod (10^9 + 7)$

int main() {
    long long n = 1000000000;
    cout << power(2, n, MOD) << endl;
    return 0;
}

Problem: Find number of ways to choose r items from n items

int main() {
    precompute();
    int n = 100000, r = 50000;
    cout << nCr(n, r) << endl;
    return 0;
}

Problem: Find $(a \times b^{-1}) \mod m$

int main() {
    long long a = 10, b = 3;
    long long result = divMod(a, b);
    // result is the value such that (result * 3) % MOD == 10
    cout << result << endl;
    return 0;
}

Why $10^9 + 7$?

1. It’s prime - Makes finding modular inverse easy
2. Fits in 32-bit - $10^9 + 7 < 2^{30}$
3. Multiplication won’t overflow 64-bit - $(10^9)^2 < 2^{63}$

Summary

Operation	Formula	Code
Addition	$(a+b) \mod m$	(a + b) % MOD
Subtraction	$(a-b+m) \mod m$	(a - b + MOD) % MOD
Multiplication	$(a \times b) \mod m$	(a * b) % MOD
Exponentiation	$a^n \mod m$	power(a, n, MOD)
Division	$a \times b^{-1} \mod m$	a * modInverse(b) % MOD
Inverse	$a^{m-2} \mod m$	power(a, MOD-2, MOD)
nCr	$\frac{n!}{r!(n-r)!} \mod m$	fact[n] * invFact[r] * invFact[n-r]

💡 Tip: Pre-compute factorial and inverse factorial in advance if you need to calculate nCr multiple times.