Math & Number Theory

How to think about it

Number theory problems test whether you can keep arithmetic safe under modulus and exploit multiplicative structure. The two habits that matter most: (1) take % m after every multiplication so intermediate products never overflow; (2) use modular exponentiation (binary exponentiation: square-and-multiply) to compute a^b mod m in O(log b), never call a naive pow and pray.

For primes, the Sieve of Eratosthenes is the default: a boolean array of size n+1, cross out multiples of each prime starting from p*p. For GCD, Euclid’s algorithm is a one-liner: gcd(a, b) = b === 0 ? a : gcd(b, a % b). LCM is a / gcd(a, b) * b (divide first to avoid overflow). For n choose k mod m, precompute factorials and inverse factorials modulo m (Fermat if m is prime).

Template shapes

Shape	Core move	Example
Modular exponent	Square-and-multiply, take mod each step	LC 50, LC 372
Sieve	Boolean array, cross out from p*p	LC 204
GCD / LCM	Euclid: gcd(b, a % b)	LC 1071, LC 365
Factorials / divisibility	Trailing zeros, factor counting, combinatorics mod m	LC 172

Complexity baseline

Modular exponent: O(log b). Sieve: O(n log log n). GCD: O(log min(a, b)). Precomputed factorials: O(n) setup, O(1) per query.

From template to problem

1. Identify the operation: exponent, prime test, GCD, or combinatorics.
2. Determine the modulus, is it prime (Fermat applies)? Is it large?
3. Take % m at every step to prevent overflow.
4. Precompute (factorials, sieve) only if the problem amortizes over many queries.

/** Math template: modular exponentiation + GCD via Euclid. */

export function modPow(base: number, exp: number, mod: number): number {
  let result = 1n;
  let b = BigInt(base) % BigInt(mod);
  const m = BigInt(mod);
  let e = BigInt(exp);
  while (e > 0n) {
    if (e & 1n) result = (result * b) % m;
    b = (b * b) % m;
    e >>= 1n;
  }
  return Number(result);
}

export function gcd(a: number, b: number): number {
  a = Math.abs(a); b = Math.abs(b);
  while (b) { [a, b] = [b, a % b]; }
  return a;
}

export function lcm(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return Math.abs(a) / gcd(a, b) * Math.abs(b);
}

/** Math template: modular exponentiation + GCD via Euclid. */

export function modPow(base: number, exp: number, mod: number): number {
  let result = 1n;
  let b = BigInt(base) % BigInt(mod);
  const m = BigInt(mod);
  let e = BigInt(exp);
  while (e > 0n) {
    if (e & 1n) result = (result * b) % m;
    b = (b * b) % m;
    e >>= 1n;
  }
  return Number(result);
}

export function gcd(a: number, b: number): number {
  a = Math.abs(a); b = Math.abs(b);
  while (b) { [a, b] = [b, a % b]; }
  return a;
}

export function lcm(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return Math.abs(a) / gcd(a, b) * Math.abs(b);
}