Math & Number Theory

01 / The shared mechanism

Many problems hide a number-theoretic backbone. Once you recognize the divisibility / modular / multiplicative structure the input really has, an O(N) loop collapses to O(log N) or O(N log log N). Three classic sub-patterns: gcd by Euclidean reduction, modular power by exponent-bit doubling, prime sieve by marking multiples once.

01 / The one-sentence essence

Halve the exponent each iteration. The binary representation of exp picks which squarings contribute to the result — O(log exp) instead of O(exp).

Problemcompute aⁿ mod Ma3n13M100

Compute 3^13 mod 100. Binary expansion of exp = 1011 (low bit first). Start with result = 1, base = 3 % 100.

step

0 / 12

bit i

—

base

result

0 / 12

base, exp, mod

02 / The pattern signature

# compute (base^exp) mod M in O(log exp)result ← 1base ← base % Mwhile exp > 0:if exp & 1: # lowest bit of exp is 1result ← (result × base) % Mbase ← (base × base) % M # squareexp ← exp >> 1 # drop the bit we just usedreturn result

03 / When to recognize this pattern

"large modular exponent / aⁿ mod M"

The canonical use. LC 50 (pow(x, n) for floats — same skeleton with negative exponent handling), LC 372 super-pow. Anytime you see aⁿ mod M with n too large to loop, this is it.

"modular multiplicative inverse via Fermat's little theorem"

When the modulus p is prime, a⁻¹ ≡ a^(p−2) (mod p). So you don't need extended Euclidean — one fast-pow call gives you the inverse, which unlocks division under a prime modulus (binomial coefficients, combinatorics counts).

"matrix exponentiation"

The same skeleton, but replace × with matrix multiply and start result at the identity matrix. That's how you compute the N-th Fibonacci / N-th term of any linear recurrence in O(k³ log N).

"super-pow / nested exponent"

LC 372. When the exponent itself is a huge digit array b = [b₀, b₁, …], use a^b = (a^(b/10))^10 · a^(b mod 10) and recurse. Each level uses modular power on a tiny exponent (≤ 10).

04 / Common pitfalls

Forgetting % M after a multiplication.

base * base already lives in [0, M²) — without an immediate % M the values overflow 64-bit ints after just a couple of squarings. Always take the modulus right where the multiplication happens, not later.

ii.

Multiplying result when the bit is 0.

The whole point of the trick is that only the set bits of exp contribute. If you fold result *= base unconditionally you're computing base^(number of iterations), which is plain wrong. Gate the multiply with if exp & 1.

iii.

Special-casing exp == 0 incorrectly.

With result = 1 as the initial value the loop body never executes when exp == 0, so you correctly return 1 — including the 0⁰ case, which is conventionally 1 in this context. Don't add a guard that returns 0 for exp == 0.

05 / Go practice — on LeetCode

Four problems. LC 50 is the canonical float version of the same skeleton; the rest are modular-arithmetic flavours where the exponent is enormous and looping is impossible.

01Pow(x, n)— LC 50medium→02Super Pow— LC 372medium→03Count Good Numbers— LC 1922medium→04Count Collisions of Monkeys on a Polygon— LC 2550medium→

— / When to use which

gcd / lcm

Use whenever divisibility is the heart of the problem — common factor, coprimality test, simplest fraction, LCM via a · b / gcd(a, b). Euclid's identity gcd(a, b) = gcd(b, a % b) drops each step geometrically.

Euclidean · LC 1071 · LC 1979

modular power

Use whenever you need aⁿ mod M for huge n, or a multiplicative inverse mod a prime. Halve the exponent each step; the bit pattern of n picks which squarings contribute. O(log n) instead of O(n).

exponent halving · LC 50 · LC 372

prime sieve

Use when you need all primes up to N (or all smallest prime factors). For each prime p walk its multiples and mark them composite — every composite is marked O(log log N) times amortized.

Eratosthenes · LC 204 · LC 952