Math Primer

Math Primer — Competitive Programming

1. Modular Arithmetic (The Lifeblood of CF)

Core Rules

(a + b) % MOD = (a % MOD + b % MOD) % MOD
(a - b) % MOD = (a % MOD - b % MOD + MOD) % MOD    // +MOD to avoid negative
(a * b) % MOD = (a % MOD * b % MOD) % MOD
(a / b) % MOD = (a % MOD * modInv(b)) % MOD          // NOT division! Use modular inverse

Modular Exponentiation (powMod)

func modPow(a, b, mod int64) int64 {
    res := int64(1)
    a %= mod
    for b > 0 {
        if b&1 == 1 { res = res * a % mod }
        a = a * a % mod
        b >>= 1
    }
    return res
}

Complexity: O(log b)

Modular Inverse

When MOD is prime (1e9+7 is prime): modInv(a) = modPow(a, MOD-2, MOD) — Fermat's Little Theorem

const MOD = 1000000007
func modInv(a int64) int64 { return modPow(a, MOD-2, MOD) }

Precomputing Factorials & nCr

const MAXN = 200000
var fact, invFact [MAXN + 1]int64

func precompute() {
    fact[0] = 1
    for i := 1; i <= MAXN; i++ { fact[i] = fact[i-1] * int64(i) % MOD }
    invFact[MAXN] = modPow(fact[MAXN], MOD-2, MOD)
    for i := MAXN; i >= 1; i-- { invFact[i-1] = invFact[i] * int64(i) % MOD }
}

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

2. Number Theory

GCD & LCM (Built-in in Go 1.20+)

func gcd(a, b int) int { for b != 0 { a, b = b, a%b }; return a }
func lcm(a, b int) int { return a / gcd(a, b) * b }

Prime Sieve (Eratosthenes)

const MAXV = 1000000
var isPrime [MAXV + 1]bool
func sieve() {
    for i := 2; i <= MAXV; i++ { isPrime[i] = true }
    for i := 2; i*i <= MAXV; i++ {
        if isPrime[i] {
            for j := i * i; j <= MAXV; j += i { isPrime[j] = false }
        }
    }
}

Optimized variant: Only iterate odd numbers after 2. Memory: bitset.

Prime Factorization (Trial Division)

func factorize(n int) map[int]int {
    res := map[int]int{}
    for i := 2; i*i <= n; i++ {
        for n%i == 0 { res[i]++; n /= i }
    }
    if n > 1 { res[n]++ }
    return res
}

Divisor Enumeration

func getDivisors(n int) []int {
    res := []int{}
    for i := 1; i*i <= n; i++ {
        if n%i == 0 {
            res = append(res, i)
            if i != n/i { res = append(res, n/i) }
        }
    }
    sort.Ints(res)
    return res
}

GCD Properties (Crucial for CF)

gcd(a, b) = gcd(a-b, b) — Euclidean algorithm foundation
gcd(a, b) = gcd(a % b, b)
gcd(a, b) * lcm(a, b) = a * b
gcd(a1, a2, ..., an) = gcd(a1, gcd(a2, ..., an))
If gcd(a, b) = 1, a and b are coprime
gcd(a, a+1) = 1 — consecutive integers are always coprime
gcd(a, b) = gcd(a, a+b) — adding doesn't change gcd

3. Combinatorics

Key Formulas

Concept	Formula	Notes
Permutations	`P(n, r) = n! / (n-r)!`	Ordered arrangements
Combinations	`C(n, r) = n! / (r! * (n-r)!)`	Unordered selections
Stars and Bars	`C(n + k - 1, k - 1)`	Distribute n identical items into k bins
Binomial Theorem	`(x + y)^n = Σ C(n, k) * x^k * y^(n-k)`
Catalan Numbers	`C_n = C(2n, n) / (n + 1)`	Valid parens, BSTs, lattice paths

Common Counting Patterns

"At least one" → Total − None (complement counting)
Pigeonhole principle: n items into m boxes, one box has at least ceil(n/m)
Inclusion-Exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|
Parity tricks: parity of nCr(n, k) — even iff (k & (n-k)) != 0 (Lucas' theorem special case)

4. Binary Search on Answer (CF Favorite)

Not searching an array — searching the answer space.

// Find minimum X such that f(X) is true
lo, hi := 0, int(1e18)  // or math.MaxInt64
for lo < hi {
    mid := lo + (hi-lo)/2
    if f(mid) { hi = mid } else { lo = mid + 1 }
}
return lo

When to use: "minimize maximum", "maximum minimum", maximize/minimize something with monotonic predicate.

5. Prefix Sums & Difference Arrays

1D Prefix Sum

pref := make([]int, n+1)
for i := 0; i < n; i++ { pref[i+1] = pref[i] + arr[i] }
// sum[l..r] = pref[r+1] - pref[l]

Difference Array (Range Updates)

diff := make([]int, n+2)  // 1-indexed
// add v to [l, r]:
diff[l] += v; diff[r+1] -= v
// restore:
for i := 1; i <= n; i++ { arr[i] = arr[i-1] + diff[i] }

2D Prefix Sum

pref := make([][]int, n+1)
for i := 1; i <= n; i++ {
    for j := 1; j <= m; j++ {
        pref[i][j] = grid[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]
    }
}
// sum of rectangle (r1,c1) to (r2,c2):
// pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]

6. Common CF Math Tricks

Trick	Pattern
Parity	Sum/difference parity: `(a+b) % 2 == (a%2) ^ (b%2)`
Remainder	`(a + k*MOD) % MOD = a % MOD` — wrap negative to positive
Alternating sum	Group elements into pairs or compute diff array
Median minimization	Sum of absolute deviations minimized at median
Meet in the middle	Split array into 2 halves when n ≤ 40 (2^(n/2) works)
Contribution	Count how many subarrays/subsequences each element contributes to
Sweep line	Sort events by coordinate, process in order
Two pointers + monotonic	If a condition is monotonic with increasing pointer
Mex tricks	MEX of array can be computed in O(n) with set; MEX after operations often periodic
Modulo cycles	If MOD results repeat (e.g., prefix sums mod k), handle cycles

7. Fast I/O (Critical for CF)

// Go
import (
    "bufio"
    "os"
    "strconv"
)
var sc = bufio.NewScanner(os.Stdin)
var bw = bufio.NewWriter(os.Stdout)

func init() {
    sc.Split(bufio.ScanWords)
    sc.Buffer(make([]byte, 1<<20), 1<<20)
}

func nextInt() int {
    sc.Scan()
    v, _ := strconv.Atoi(sc.Text())
    return v
}

func nextString() string { sc.Scan(); return sc.Text() }

// In main:
// for t := nextInt(); t > 0; t-- { ... }
// bw.Flush()

← Previous

Editorial Log

Plan