Concepts174
Category
Fast Exponentiation
Fast exponentiation (binary exponentiation) computes a^n using repeated squaring in O(log n) multiplications.
Chinese Remainder Theorem
The Chinese Remainder Theorem (CRT) reconstructs an integer from its remainders modulo pairwise coprime moduli and guarantees a unique answer modulo the product.
Linear Sieve
The linear sieve builds all primes up to n in O(n) time by ensuring each composite is marked exactly once by its smallest prime factor (SPF).
Prime Factorization
Prime factorization expresses any integer greater than 1 as a product of primes raised to powers, uniquely up to ordering.
Extended Euclidean Algorithm
The Extended Euclidean Algorithm finds integers x and y such that ax + by = gcd(a, b) while also computing gcd(a, b).
Sieve of Eratosthenes
The Sieve of Eratosthenes marks multiples of each prime to find all primes up to n in O(n log log n) time.
GCD and Euclidean Algorithm
The greatest common divisor (gcd) of two integers is the largest integer that divides both without a remainder.
Randomized Algorithms
Randomized algorithms use coin flips (random bits) to guide choices, often making code simpler and fast on average.
Matrix Exponentiation
Matrix exponentiation turns repeated linear transitions into a single fast power of a matrix using exponentiation by squaring.
Small-to-Large Merging
Small-to-large merging is a technique where you always merge the smaller container into the larger one to guarantee low total work.
Mo's Algorithm
Mo's algorithm answers many range queries offline by reordering them to minimize pointer movement along the array.
Pick's Theorem
Pick's Theorem connects area and lattice-point counts for any simple polygon with integer-coordinate vertices.