Concepts318
Category
Sqrt Decomposition on Queries
Sqrt decomposition on queries (time blocking) processes Q operations in blocks of size about \(\sqrt{Q}\) to balance per-query overhead and rebuild cost.
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).
Polynomial Operations
Fast polynomial operations treat coefficients like numbers but use FFT/NTT to multiply in O(n \log n) time instead of O(n^2).
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.
Parallel Binary Search
Parallel Binary Search (PBS) lets you binary-search the answers of many queries at once by batching them by their current mid value.
Convolution Applications
Convolution turns local pairwise combinations (like matching characters or adding two dice) into a single fast transform–multiply–inverse pipeline.
NTT (Number Theoretic Transform)
The Number Theoretic Transform (NTT) is an FFT-like algorithm that performs discrete convolutions exactly using modular arithmetic instead of floating-point numbers.
Randomized Algorithms
Randomized algorithms use coin flips (random bits) to guide choices, often making code simpler and fast on average.
FFT (Fast Fourier Transform)
FFT converts a polynomial from coefficients to values at the n-th roots of unity in O(n log n) time, enabling fast multiplication via pointwise products.