Pattern Reference
Math
"Number theory, combinatorics, Euclidean gcd/lcm, modular arithmetic, prime sieve."
Loading...
Deep Dive Tutorial
Math problems in competitive programming are about recognizing which mathematical structure underlies the problem, then applying the right algorithm. The same 10-15 techniques appear over and over. Once you internalize GCD/LCM, the Sieve, modular arithmetic, and fast exponentiation, the vast majority of math problems become mechanical.
Essential Algorithms
GCD (Euclidean) and LCM
// GCD: gcd(a, b) = gcd(b, a % b), base case gcd(a, 0) = a
function gcd(a, b) {
while (b) [a, b] = [b, a % b];
return a;
}
// LCM: lcm(a, b) = a * b / gcd(a, b)
// Divide BEFORE multiplying to avoid overflow
function lcm(a, b) {
return (a / gcd(a, b)) * b;
}
// GCD of array: reduce with gcd
const gcdArray = (arr) => arr.reduce(gcd);Sieve of Eratosthenes — find all primes ≤ n in O(n log log n)
function sieve(n) {
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (let j = i * i; j <= n; j += i)
isPrime[j] = false;
}
}
return isPrime;
}
// isPrime[x] = true iff x is prime
// All primes: Array.from({length: n+1}, (_, i) => i).filter(i => isPrime[i])Fast exponentiation — a^b mod m in O(log b)
function powMod(base, exp, mod) {
let result = 1n;
base = BigInt(base) % BigInt(mod);
exp = BigInt(exp);
mod = BigInt(mod);
while (exp > 0n) {
if (exp % 2n === 1n) result = result * base % mod;
exp >>= 1n;
base = base * base % mod;
}
return Number(result);
}
// Standard trick: if exp is odd, multiply result by base
// Then square base and halve exp each iterationModular inverse (Fermat's little theorem — mod must be prime)
// a^(-1) mod p = a^(p-2) mod p (only works when p is prime)
function modInverse(a, p) {
return powMod(a, p - 2, p);
}
// Usage: a/b mod p = a * modInverse(b, p) mod p
// Never do (a / b) % p directly — division doesn't distribute over modnCr mod p — precompute factorials
const MOD = 1_000_000_007n;
const MAX = 200001;
const fact = new Array(MAX).fill(0n);
const inv_fact = new Array(MAX).fill(0n);
function precompute() {
fact[0] = 1n;
for (let i = 1; i < MAX; i++) fact[i] = fact[i-1] * BigInt(i) % MOD;
inv_fact[MAX-1] = powModBig(fact[MAX-1], MOD - 2n, MOD);
for (let i = MAX - 2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * BigInt(i+1) % MOD;
}
function nCr(n, r) {
if (r < 0 || r > n) return 0n;
return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}Pattern Recognition Table
| See This | Algorithm |
|---|---|
| "divisible by / GCD of" | Euclidean GCD |
| "count primes up to n" | Sieve of Eratosthenes |
| "a^b mod p" or large exponents | Fast exponentiation |
| "number of ways" with large n | nCr mod p with precomputed factorials |
| "sum of divisors / number of divisors" | Factorize using sqrt, use formula |
| Fibonacci n-th term for large n | Matrix exponentiation or Binet's formula |
| Linear recurrence for large n | Matrix exponentiation in O(k³ log n) |
Worked Problems
More Worked Problems
lightbulb
Modular arithmetic rule of thumb: Whenever a problem involves factorials, combinations, or counting paths mod 10^9+7 (a prime), you need:
1. Precomputed factorials up to MAX
2. Precomputed modular inverses of factorials
3. nCr(n, r) = fact[n] * inv_fact[r] * inv_fact[n-r] mod p
Math tricks to remember:
- GCD: Euclidean algorithm
- Sieve: Eratosthenes in O(n log log n) — start marking from p²
- Median minimizes L1 (sum of abs deviations); mean minimizes L2
- Fast power: x^n in O(log n) via repeated squaring
1. Precomputed factorials up to MAX
2. Precomputed modular inverses of factorials
3. nCr(n, r) = fact[n] * inv_fact[r] * inv_fact[n-r] mod p
Math tricks to remember:
- GCD: Euclidean algorithm
gcd(a,b) = b===0 ? a : gcd(b, a%b)- Sieve: Eratosthenes in O(n log log n) — start marking from p²
- Median minimizes L1 (sum of abs deviations); mean minimizes L2
- Fast power: x^n in O(log n) via repeated squaring