Math & number theory

1 · Why math problems matter — the constraint is the diagnosis

Most patterns earn their place through cleverness — the right data structure, the right invariant, the right traversal order. Math earns its place differently. When the input size is 10⁹ or beyond, no clever data structure rescues you. Even an O(n) linear scan does a billion iterations per call — ten seconds in a tight Go loop, far over any reasonable time limit. An O(n log n) sort is twenty seconds. The only viable complexity classes at that input size are O(log n), O(√n), and O(1). All three almost always mean math.

The flip side is just as useful. Surprisingly small N — say, N ≤ 10 or N ≤ 60 — often hides a closed-form solution that's begging to be derived. The interviewer made N small because the answer doesn't depend on iterating; it depends on noticing a combinatorial identity or a recurrence with a known formula. "N = 30 means the answer fits in a single int but the loop is too long to enumerate" is the classic Fibonacci / Catalan / Stirling tell.

• The senior-interview signal. Constraint n ≤ 10^9 or larger is almost always a math problem (or binary search on the answer, which is its first cousin). Reading the constraint line before the problem text and naming it out loud — "this is going to need fast exponentiation or a closed form, no scan will fit" — is a clear L5+ signal. Interviewers at numerics-heavy teams (search ranking, billing, ads, quant) listen for this specifically.
• Two flavours of math problem. (1) The input is huge and you need a sub-linear algorithm — fast power, GCD, Miller-Rabin. (2) The input is tiny but the search space is exponential — Catalan numbers, combinatorial identities, generating functions. The diagnosis is the same: read the constraints first.
• The "modulo 10⁹ + 7" signal. The answer is too large to fit in 64 bits, and the problem wants the answer modulo a prime. That tells you (a) the answer involves multiplication of many factors, (b) you need modular inverse (Fermat's little theorem since 10⁹+7 is prime), and (c) the final algorithm is going to be combinatorial DP plus modular arithmetic.

The math toolkit at a glance

2 · How to recognise it

Math problems rarely advertise themselves. The constraint line is the tell — it's where you should look first.

• Constraints in the billions or beyond. n ≤ 10⁹, 10¹², or 10¹⁸. Even an O(n) scan is too slow at 10⁹; an O(log n) or O(√n) approach is the only option, and that almost always means math.
• Prime, divisor, or multiple in the prompt. "Count primes up to n", "find the kth divisor", "smallest multiple of x and y". Sieve, GCD, or factorisation territory.
• "Return the answer modulo 10⁹ + 7." Says outright that the answer is huge and arithmetic happens under a prime modulus. Modular inverse, fast power, careful multiplication.
• Power computations: xⁿ, a^b mod m. Fast exponentiation in O(log n) — never a loop.
• Obvious brute force is too slow and no data structure fits. If you can't see where a heap, hash map, or tree would help, and the brute force is O(n) on a 10⁹ input, the trick is mathematical.

3 · Canonical example — Pow(x, n) (LC 50)

Problem. Implement pow(x, n) — compute x raised to the integer n. The naive loop multiplies x by itself n times, which is O(n). With n up to 2³¹, that's two billion multiplications. Fast exponentiation does it in O(log n) — about 31 multiplications at the same bound.

Input:  x = 2.0, n = 10
Output: 1024.0

Input:  x = 2.0, n = -2
Output: 0.25
Explanation: 2^-2 = 1 / 2^2 = 0.25

The idea: xⁿ = (x²)^n/2 when n is even, and x · xⁿ⁻¹ when n is odd. Each step at least halves n, so the total work is logarithmic. Negative exponents flip to the reciprocal: x⁻ⁿ = (1/x)ⁿ.

4 · Reference implementation

Iterative fast power. Walk the bits of n from the bottom; if a bit is set, multiply the running result by the current square; square the base each iteration regardless.

def fast_pow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n > 0:
        if n & 1:           # bit set: multiply result by current power of x
            result *= x
        x *= x              # square the base
        n >>= 1             # consume the bit
    return result

The other three tools that round out the math toolkit:

# Euclid's GCD — O(log(a + b))
def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

# LCM falls out of GCD
def lcm(a: int, b: int) -> int:
    return a // gcd(a, b) * b   # divide first to avoid overflow

# Sieve of Eratosthenes — O(N log log N), N up to ~10^7 comfortably
def sieve(n: int) -> list[int]:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i, p in enumerate(is_prime) if p]

# Integer square root by <a class="il" href="/codex/problem-solving/patterns/binary-search">binary search</a> — O(log n), no float precision loss
def isqrt(n: int) -> int:
    if n < 2: return n
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

5 · Variations

A small toolkit; each entry is its own technique. The right one usually falls out of the wording once you know what to look for.

5a · Euclidean GCD, traced

Euclid's algorithm for gcd(a, b) = gcd(b, a mod b) until b = 0. On gcd(252, 105):

5b · The math primitives, named

6 · Five-problem progression

7 · Sister algorithms

The five primitives on this page are the workhorse. Eight more techniques sit one step beyond them — each one is what you reach for when the workhorse doesn't quite close the problem. Knowing the names alone is enough to recognise the problem; the implementation details are looked up.

• Pollard rho (factorisation). When you need the prime factors of a single 64-bit integer (10¹⁸ range), Pollard rho factors in expected O(n^(1/4)) time — vastly faster than trial division at O(√n). The algorithm finds non-trivial factors by detecting cycles in f(x) = x² + c (mod n). Standard in cryptanalysis homework and in competitive programming when factorisation is needed inside a hot loop. Composes with Miller-Rabin to factor any 64-bit integer in milliseconds.
• Miller-Rabin primality. Probabilistic prime test for huge n. For a 64-bit integer, the deterministic version with witnesses {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} is exact. Costs O(k · log³ n) per test where k is the number of witnesses; far better than the O(√n) trial division when n is large. Used everywhere from RSA key generation to "is this n prime?" queries inside DP transitions.
• Linear sieve. The classical Sieve of Eratosthenes is O(N log log N); a small modification (mark each composite exactly once, via its smallest prime factor) drops it to O(N) and produces the smallest-prime-factor array for free as a side product. The SPF array lets you factor any number up to N in O(log N) by repeated division. Worth knowing when you'll do many factorisation queries.
• Chinese Remainder Theorem (CRT). Given simultaneous congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ... with pairwise coprime moduli, CRT reconstructs the unique x mod m₁m₂…. Shows up in calendar problems ("the next year where Jan 1 is a Tuesday and Easter falls on…"), cryptography (RSA decryption is 4× faster via CRT), and any problem where you need to combine modular partial answers.
• Extended Euclidean algorithm. Returns not just gcd(a, b) but also Bézout coefficients (x, y) with a·x + b·y = gcd(a, b). The building block for modular inverse when the modulus is not prime (so Fermat doesn't apply) and for CRT. Twenty lines; worth memorising the recursion.
• Modular inverse via Fermat vs Extended Euclidean. Two routes to the same destination. (a) Fermat's little theorem: when p is prime and gcd(a, p) = 1, a^(p-2) ≡ a^(-1) (mod p) — compute via fast exponentiation in O(log p). Pretty, short, requires prime modulus. (b) Extended Euclidean: works for any modulus where gcd(a, m) = 1. Same complexity, more general. Use Fermat when the problem says "mod 10⁹+7"; use extended Euclidean for composite moduli.
• Catalan numbers. The sequence C_n = (2n choose n) / (n + 1) counts: balanced parenthesisations, binary trees with n internal nodes, monotonic lattice paths, mountain ranges of width 2n. When a problem asks "in how many distinct ways can you parenthesise / split / nest…", the answer is usually a Catalan number. Recurrence C_(n+1) = Σ C_i · C_(n-i) — the "split into two halves and recurse" structure.
• Stirling numbers (first and second kind). Stirling of the second kind S(n, k) counts the number of ways to partition n labelled items into k non-empty unlabelled subsets. Appears in "distribute n distinct balls into k identical boxes, no box empty" problems. First kind counts permutations by cycle structure. Less common than Catalan, but the giveaway is "partition into k unlabelled groups".
• Möbius function and Möbius inversion. The Möbius function μ(n) is +1 for square-free n with an even number of prime factors, -1 for odd, 0 for non-square-free. The Möbius inversion formula lets you go from f(n) = Σ g(d) (sum over divisors d of n) to g(n) = Σ μ(d) f(n/d). Used in counting problems with "coprime to n" or "exactly k distinct prime factors" conditions.

8 · Worked example — LC 204 Count Primes (Sieve of Eratosthenes)

Problem. Given n, return the count of prime numbers strictly less than n. Constraint: 0 ≤ n ≤ 5·10^6. Trial division is O(n · √n) — ~10¹⁰ operations at the limit, way too slow. The sieve runs in O(n log log n), about 2·10^7 operations.

Input:  n = 10
Output: 4
Explanation: primes below 10 are 2, 3, 5, 7.

The sieve, end to end

Start with a boolean array isPrime[0..n-1] all true. Mark 0 and 1 as not prime. For each i from 2 up to √n, if isPrime[i] is still true, mark every multiple of i starting at i*i as not prime. Count remaining true entries.

func countPrimes(n int) int {
    if n < 2 {
        return 0
    }
    isPrime := make([]bool, n)
    for i := 2; i < n; i++ {
        isPrime[i] = true
    }
    for i := 2; i*i < n; i++ {
        if isPrime[i] {
            // Start at i*i — all smaller multiples were marked by smaller primes
            for j := i * i; j < n; j += i {
                isPrime[j] = false
            }
        }
    }
    count := 0
    for i := 2; i < n; i++ {
        if isPrime[i] {
            count++
        }
    }
    return count
}
// Time:  O(n log log n) — the sum of harmonic series over primes
// Space: O(n) for the boolean array

Why start the inner loop at i*i

Every composite k < i² that has i as a factor also has a smaller prime factor (namely the cofactor k / i < i), so it was already marked when the outer loop processed that smaller prime. Starting at i² skips redundant work. It's a constant-factor win but it changes the complexity from "feels slow" to "fast enough for n = 10⁷".

9 · Worked example — LC 372 Super Pow (modular fast exponentiation with a mod chain)

Problem. Compute a^b mod 1337 where b is given as an array of digits (b can be astronomically large — millions of digits). Standard fast exponentiation needs b as a number, not a digit array. The trick is to compute it digit-by-digit using the identity a^(10x + d) = (a^x)^10 · a^d.

Input:  a = 2, b = [1, 0]   (representing 10)
Output: 1024

Input:  a = 2147483647, b = [2, 0, 0]   (representing 200)
Output: 1198

The decomposition

Read the digits of b left to right. Maintain a running result. At each digit d, the new exponent is (oldExp · 10) + d, so the result transforms as result = (result^10) · (a^d). Each step is two fast exponentiations modulo 1337 — a constant amount of work per digit.

const MOD = 1337

func superPow(a int, b []int) int {
    a = a % MOD
    result := 1
    for _, d := range b {
        // result becomes (result^10) * (a^d), all mod MOD
        result = mulMod(powMod(result, 10), powMod(a, d))
    }
    return result
}

// Fast exponentiation: a^n mod MOD in O(log n)
func powMod(a, n int) int {
    a %= MOD
    result := 1
    for n > 0 {
        if n&1 == 1 {
            result = (result * a) % MOD
        }
        a = (a * a) % MOD
        n >>= 1
    }
    return result
}

func mulMod(x, y int) int {
    return (x * y) % MOD
}
// Time:  O(|b| · log 10) = O(|b|) — constant per digit
// Space: O(1)

Why this works — the algebra

Let b = b_k b_(k-1) … b_1 b_0 as decimal digits. Reading left to right, after processing prefix b_k … b_j, the value of that prefix is P_j. The next digit gives a new prefix value P_(j-1) = 10·P_j + b_(j-1). So a^(P_(j-1)) = a^(10·P_j) · a^(b_(j-1)) = (a^(P_j))^10 · a^(b_(j-1)). The mod stays well-defined throughout because MOD is a constant integer.

10 · Worked example — LC 458 Poor Pigs (HARD — information theory)

Problem. You have n buckets, exactly one of which contains poison. You have pigs; a pig drinks from a subset of buckets, takes minutesToDie to die after drinking poison, and you have minutesToTest total time to find the poisoned bucket. Return the minimum number of pigs needed. Example: buckets = 1000, minutesToDie = 15, minutesToTest = 60 — answer is 5 pigs.

Why this is information theory, not simulation

• How many tests per pig? tests = minutesToTest / minutesToDie. With 60 / 15 = 4, each pig can be observed at 4 distinct test moments. Each pig's outcome is one of tests + 1 states: died after test 1, after test 2, …, after test 4, or survived. So each pig encodes log_2(tests + 1) bits — here, log_2(5).
• How many bits do we need? log_2(n) bits to identify one of n buckets. Here, log_2(1000) ≈ 9.97 bits.
• How many pigs? Smallest p such that (tests + 1)^p ≥ n. Equivalently p = ⌈log_(tests+1)(n)⌉. For 1000 buckets at 5 states per pig: 5^4 = 625 < 1000 ≤ 5^5 = 3125, so p = 5.
• The construction. Label buckets with a base-(tests+1) number with p digits. Pig i drinks from every bucket whose i-th digit is 1, then again from every bucket whose i-th digit is 2 in the next test slot, and so on. The death-time of each pig gives one digit of the poisoned bucket's label.

Go implementation

import "math"

func poorPigs(buckets, minutesToDie, minutesToTest int) int {
    if buckets <= 1 {
        return 0
    }
    states := minutesToTest/minutesToDie + 1
    // Smallest p such that states^p >= buckets
    // Equivalent: p = ceil(log(buckets) / log(states))
    pigs := 0
    pow := 1
    for pow < buckets {
        pow *= states
        pigs++
    }
    return pigs
}
// Time:  O(log_states buckets) — at most ~30 iterations
// Space: O(1)

// Float version (faster on large inputs, watch precision)
func poorPigsFloat(buckets, minutesToDie, minutesToTest int) int {
    states := minutesToTest/minutesToDie + 1
    return int(math.Ceil(math.Log(float64(buckets)) / math.Log(float64(states))))
}

11 · Recognition checklist

Read the constraint line and the prompt's exact wording before anything else. The table below maps signal phrases to the most likely tool. When more than one match, the highest-N constraint wins.

12 · How to solve hard math problems, step-by-step

1. Compute outputs for small inputs by brute force. The first thing to do on any "find a single integer" math problem is to write a stupid O(n!) or O(2^n) brute force and print f(0), f(1), …, f(10). Look at the sequence. Is it 1, 1, 2, 3, 5, 8, …? Fibonacci. Is it 1, 1, 2, 5, 14, 42, …? Catalan. Is it 1, 2, 6, 24, 120, …? Factorial. Is it a polynomial in n? Polynomial fitting. The OEIS covers nearly everything published; a 30-second lookup can hand you the closed form before you start.
2. Check whether the answer needs mod 10^9 + 7. If yes, the answer is huge and the algorithm is going to involve repeated multiplication. Plan to apply % MOD after every multiply and every add (subtractions need (a - b + MOD) % MOD to avoid negative values). If you'll need division, you'll need a modular inverse — Fermat if the modulus is prime, extended Euclidean otherwise.
3. Decide whether fast exponentiation is needed for the size. Any time you see x^n, a^b mod m, "matrix raised to the n-th power", or a linear recurrence iterated billions of times — fast exponentiation (binary or matrix) reduces O(n) to O(log n). Linear recurrences of length k can be iterated n steps in O(k³ log n) via matrix fast exponentiation. This is how "Fibonacci of 10¹⁸" problems are solved.
4. Check for combinatorial identities. If your formula involves binomial coefficients, look for Pascal's triangle simplifications: (n choose k) = (n-1 choose k-1) + (n-1 choose k); hockey stick: Σ (i choose k) = (n+1 choose k+1); Vandermonde: Σ (m choose i)(n choose k-i) = (m+n choose k). A messy summation often collapses to one binomial coefficient via these identities. Save yourself a screen of code; spend two minutes thinking before typing.
5. Verify the closed form against the brute force. Once you derive a candidate formula, run it side by side with the brute force for n ∈ [0, 15]. Any mismatch is the formula being wrong; brute force is almost always right for small n. The "I derived this, why doesn't it pass" debug loop is much faster when you have a reference truth on hand.

12a · Walkthrough — deriving a closed form from the first 10 outputs

A concrete drill of the "brute force first, then look for a pattern" reflex from section 12. The problem: count the number of binary strings of length n with no two consecutive 1s.

Step 1 — write the brute force

func bruteForce(n int) int {
    count := 0
    for mask := 0; mask < (1 << n); mask++ {
        // Check if mask has any two consecutive 1s
        if mask&(mask>>1) == 0 {
            count++
        }
    }
    return count
}
// Time: O(n · 2^n). Fine for n ≤ 20.

Step 2 — print the first 10 values

for n := 1; n <= 10; n++ {
    fmt.Printf("n=%d: %d
", n, bruteForce(n))
}

n=1:  2
n=2:  3
n=3:  5
n=4:  8
n=5:  13
n=6:  21
n=7:  34
n=8:  55
n=9:  89
n=10: 144

Step 3 — spot the pattern

2, 3, 5, 8, 13, 21, 34, 55, 89, 144 — this is the Fibonacci sequence shifted. If you don't recognise it, paste it into OEIS; the first hit will tell you it's F(n+2) where F is the Fibonacci sequence with F(1) = F(2) = 1.

Step 4 — prove the recurrence

Now that you know the answer is F(n+2), derive it. Let a(n) be the count for length n. A valid string of length n either starts with 0 (then the rest is any valid length-(n-1) string) or starts with 10 (then the rest is any valid length-(n-2) string). So:

a(n) = a(n-1) + a(n-2)
a(1) = 2  (strings: "0", "1")
a(2) = 3  (strings: "00", "01", "10")

This is the Fibonacci recurrence. With a(1) = 2 and a(2) = 3, the sequence is F(3), F(4), F(5), … i.e. a(n) = F(n+2). Derivation matches the empirical pattern.

Step 5 — final code

func countBinaryStrings(n int) int {
    if n == 0 {
        return 1
    }
    a, b := 2, 3 // a(1), a(2)
    for i := 3; i <= n; i++ {
        a, b = b, a+b
    }
    if n == 1 {
        return a
    }
    return b
}
// Time:  O(n)
// Space: O(1)

// If n can be up to 10^18, use matrix exponentiation:
// [[a(n+1)], [a(n)]] = [[1,1],[1,0]]^n · [[a(1)], [a(0)]]
// computed in O(log n) via fast matrix power.

13 · Common pitfalls

• Integer overflow. Python's int is arbitrary precision, so the issue hides until you port to C++, Java, or Go. In a 64-bit language, two values near 10⁹ multiplied together exceed int64; use modular arithmetic or wider types.
• Forgetting the mod on every operation. Problems that say "answer modulo 10⁹ + 7" expect (a * b) % MOD after every multiplication, not just at the end. Forget once and the intermediate value overflows or becomes wrong.
• Recursive fast exponentiation. Hits Python's default recursion limit around n = 10³–10⁴. The iterative bit-walk has the same complexity and no stack issue. Default to iterative.
• Edge case n = 0 in pow. x0 = 1 for every x, including 0 by convention in most problems. Initialise result = 1 and let the loop do nothing.
• Off-by-one in sieve bounds. The inner loop should start at i * i, not 2 * i, and the outer loop runs up to √n inclusive. The list is size n + 1 so index n is valid.
• Negative input to GCD. Euclid's algorithm assumes non-negative operands. Take absolute values at the entry, or the loop terminates with a negative result and downstream LCM goes wrong.
• Integer overflow when N > 10⁹. In Go, the default int is 64-bit on 64-bit platforms — so a * b for two values near 10⁹ fits in int. But if you've forced int32 (or you're cross-checking against Python which has no overflow), the multiplication wraps silently to a negative value. The fix is explicit: declare variables as int64 when products might exceed 10¹⁸, and consider math/big.Int for arbitrarily large arithmetic. In modular code, take %MOD after every multiply to keep intermediates bounded.
• Mod arithmetic with subtraction — the negative result trap. In Go, (-3) % 7 is -3, not 4 (Go follows the C convention where modulus takes the sign of the dividend). For modular arithmetic that needs the canonical non-negative representative, write (a - b%m + m) % m instead of (a - b) % m. Forgetting this is the single most common bug in modular-arithmetic interview code.
• Modular inverse only exists when gcd(a, m) = 1. If the modulus is composite and your a shares a factor with m, no inverse exists — Fermat doesn't apply (the modulus isn't prime) and extended Euclidean returns a non-1 GCD. Always state the coprimality precondition; if the problem doesn't guarantee it, you need a fallback algorithm.
• Sieve memory blowup for N > 10⁷. A boolean array of size 10^8 is 100 MB in Go (one byte per bool) — well over most judge memory limits. Switch to []uint64 as a packed bitset to drop to 12.5 MB, or use a segmented sieve to process the range in chunks. For N up to 10^12, give up on the sieve and use Miller-Rabin per query.
• Float precision in math.Pow / math.Log. math.Pow(10, 18) returns 9.999999999999998e+17 on some inputs because of float rounding. Don't use math.Pow for integer powers; write fast exponentiation. Don't use math.Log to compute ⌈log_b(n)⌉ exactly — multiply up instead and count iterations (see LC 458 above). Float math is a footgun in number theory problems.
• Off-by-one in inclusive/exclusive bounds. "Count primes < n" (LC 204) vs. "≤ n". "Find the kth divisor" — is k 0-indexed or 1-indexed? Read carefully. Sample inputs are your friend; if your code outputs the right answer for the sample but the wrong one for the next test, the bug is almost always an off-by-one at the bound.

14 · What to say in the interview

1. "The constraints are huge, so this is a math problem." Read the constraint line out loud. If n is 10⁹ or beyond, name it — the interviewer wants to hear you reach that conclusion.
2. Name the specific tool. "Fast exponentiation in O(log n)." "Sieve in O(N log log N)." "Euclid's GCD in O(log(a + b))." The pattern is "math"; the move is one of five or six.
3. State the complexity in the right units. Math problems are measured in log n or √n, not n. Saying "O(log n)" up front tells the interviewer you understand why the brute force fails.
4. Call out modular arithmetic if the answer is huge. "I'll take the mod after every multiplication to keep the intermediate values bounded." The interviewer is listening for this specifically on any "modulo 10⁹ + 7" problem.
5. Edge cases to mention. n = 0, n = 1, negative inputs, the largest value of n the prompt allows. These three together cover most off-by-ones in this family.

15 · Where this gets asked

16 · Try it yourself

Pow(x, n) · LC 50

Fast exponentiation. Hint: if n is even, pow(x, n) = pow(x*x, n/2); if odd, pow(x, n) = x * pow(x, n-1). Handle negative n by inverting at the start. O(log n).

Happy Number · LC 202

Cycle detection in a number sequence. Hint: every non-happy number falls into the cycle {4, 16, 37, 58, 89, 145, 42, 20}. Either keep a visited set, or use Floyd's tortoise-and-hare on the sum-of-squares-of-digits function.

Sqrt(x) · LC 69

Two solutions worth knowing. Hint: binary search for the largest k with k² ≤ x. Or Newton's method: k = (k + x/k) / 2 iterated until convergence. Newton converges in ~5 iterations even for huge inputs.

Multiply Strings · LC 43

Long multiplication, the way you learned in school. Hint: result has at most len(a) + len(b) digits. For each pair (i, j), add a[i] * b[j] to result[i + j + 1], then propagate carries at the end. Watch the leading-zero trim.

Stretch — Random Pick with Weight · LC 528

Prefix sum + binary search. Hint: build a prefix-sum array of weights. Generate a random number in [1, total]. Binary-search for the first prefix sum ≥ random. The index found is your weighted pick.

Further reading

• Concrete Mathematics (Graham, Knuth, Patashnik). The reference. Heavier than you need for interviews, but Chapter 4 on number theory is the cleanest treatment of GCD, modular arithmetic, and CRT in print.
• CP-Algorithms — number theory pages. Practical, code-first writeups of fast power, sieves, modular inverse, extended Euclid. The site contest programmers actually use.
• Project Euler. Free problem set, math-heavy. The first 50 problems are a near-perfect drill for the toolkit on this page.
• Khan Academy — Number Theory. Gentler entry point if the algebra feels rusty. Covers divisibility, primes, modular arithmetic from scratch.
• Adjacent: Bit manipulation. The cousin pattern. Fast exponentiation walks bits; many math problems factor through XOR, AND, popcount.
• Adjacent: Dynamic programming. Counting problems with "modulo 10⁹ + 7" are almost always DP plus modular arithmetic. Knowing both is the difference between a partial and a full solution.