Math & Number Theory

GCD and LCM

from math import gcd, lcm           # Python 3.9+

def gcd_manual(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm_manual(a, b):
    return a // gcd(a, b) * b        # divide first to avoid overflow in other languages

#include <numeric>
long long g = std::gcd(a, b);        // C++17
long long l = a / std::gcd(a, b) * b;

Euclid's algorithm is O(log min(a, b)). Uses: reducing fractions/slopes, periodicity (two cycles realign after lcm steps), string GCD, Water and Jug (target reachable iff it's a multiple of gcd).

Extended Euclid finds x, y with a·x + b·y = gcd(a, b) — used for modular inverses when the modulus isn't prime.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

Primes

Trial division — O(√n)

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def factorize(n):
    f = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f

Sieve of Eratosthenes — O(n log log n)

def sieve(n):                        # primes < n
    if n < 3:
        return []
    is_p = bytearray([1]) * n
    is_p[0] = is_p[1] = 0
    for p in range(2, int(n ** 0.5) + 1):
        if is_p[p]:
            is_p[p * p::p] = bytearray(len(range(p * p, n, p)))
    return [i for i in range(n) if is_p[i]]

vector<int> sieve(int n) {           // primes < n
    vector<bool> isP(n, true);
    vector<int> primes;
    for (int i = 2; i < n; i++) {
        if (!isP[i]) continue;
        primes.push_back(i);
        for (long long j = (long long)i * i; j < n; j += i) isP[j] = false;
    }
    return primes;
}

Smallest prime factor sieve: store spf[x] for every x ≤ n; then factorize any x ≤ n in O(log x) by repeated division. Great when you need to factorize many numbers.

Modular arithmetic

Answers that "may be large" are asked modulo M = 10⁹ + 7 (a prime).

(a + b) mod M = ((a mod M) + (b mod M)) mod M
(a · b) mod M = ((a mod M) · (b mod M)) mod M
(a − b) mod M = ((a − b) mod M + M) mod M     ← avoid negatives in C++/Java
(a / b) mod M = a · b⁻¹ mod M                  ← division needs a modular inverse

Fast (binary) exponentiation

def power(a, e, m):
    result = 1
    a %= m
    while e:
        if e & 1:
            result = result * a % m
        a = a * a % m
        e >>= 1
    return result
# Python built-in: pow(a, e, m)

long long power(long long a, long long e, long long m) {
    long long r = 1; a %= m;
    while (e) {
        if (e & 1) r = r * a % m;
        a = a * a % m;
        e >>= 1;
    }
    return r;
}

Modular inverse

For prime M, Fermat's little theorem gives b⁻¹ ≡ b^(M−2) (mod M).

inv = pow(b, M - 2, M)      # or pow(b, -1, M) in Python 3.8+

Combinatorics

nCr modulo a prime (precomputed factorials)

MOD = 10**9 + 7
N = 2 * 10**5 + 1
fact = [1] * N
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * N
inv_fact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)
for i in range(N - 1, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD

def nCr(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

const long long MOD = 1e9 + 7;
const int N = 200001;
long long fact[N], invFact[N];
void init() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    invFact[N - 1] = power(fact[N - 1], MOD - 2, MOD);
    for (int i = N - 1; i > 0; i--) invFact[i - 1] = invFact[i] * i % MOD;
}
long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

For small n without a modulus, Pascal's triangle C[n][k] = C[n−1][k−1] + C[n−1][k] or Python's math.comb.

Inclusion–exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|. Count numbers ≤ n divisible by 2 or 3: n//2 + n//3 − n//6. Generalizes with alternating signs over subsets (use bitmasks for small numbers of sets).

Matrix exponentiation

A linear recurrence of order k can be written as a k × k matrix power. Fib(n) in O(log n):

def mat_mult(A, B, mod):
    n, m, p = len(A), len(B), len(B[0])
    return [[sum(A[i][k] * B[k][j] for k in range(m)) % mod for j in range(p)] for i in range(n)]

def mat_pow(M, e, mod):
    n = len(M)
    R = [[int(i == j) for j in range(n)] for i in range(n)]
    while e:
        if e & 1:
            R = mat_mult(R, M, mod)
        M = mat_mult(M, M, mod)
        e >>= 1
    return R

def fib(n, mod=10**9 + 7):
    return mat_pow([[1, 1], [1, 0]], n, mod)[0][1]

O(k³ log n). Used when n is up to 10¹⁸ and the DP transition is fixed.

Useful identities and facts

• Sum 1..n = n(n+1)/2; sum of squares = n(n+1)(2n+1)/6.
• Geometric series: 1 + r + … + r^(n−1) = (rⁿ − 1)/(r − 1).
• Number of divisors of n = ∏(eᵢ + 1) over its prime factorization.
• There are ~n / ln n primes below n; divisor counts below 10⁹ stay under 1,344.
• Digit sum mod 9 equals the number mod 9 (Add Digits: 1 + (n − 1) % 9).
• Trailing zeros of n! = n/5 + n/25 + n/125 + …
• Reservoir sampling picks a uniform random item from a stream: keep the i-th item with probability 1/i.

Geometry essentials

def cross(o, a, b):                  # > 0: counter-clockwise turn o→a→b
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def dist2(a, b):                     # squared distance: no floating point needed
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

• Collinear points: cross product is 0. For slopes, use reduced (dy/g, dx/g) pairs instead of floats.
• Convex hull (Andrew's monotone chain): sort points, build lower and upper hulls with the cross product. O(n log n) — Erect the Fence.
• Rectangle overlap: max(left) < min(right) and max(bottom) < min(top).
• Compare distances with squared values to stay in integers.

Game theory (basics)

• A position is losing if every move leads to a winning position; winning if some move leads to a losing position. Compute with DP/memoization over states.
• Nim: the first player wins iff the XOR of pile sizes is non-zero.
• Sprague-Grundy: each independent subgame has a Grundy number (mex of reachable values); XOR them.
• Many "games" on LeetCode have a closed-form pattern (e.g. Nim Game: lose iff n % 4 == 0) — compute small cases by brute force and look for it.

Common mistakes

• Integer overflow in C++ before the modulo (a * b with both ints).
• Negative results of % in C++/Java.
• Floating-point slopes/equality — use integer fractions or cross products.
• Recomputing factorials per query instead of precomputing.
• Forgetting that 1 is not prime and 2 is.