Concepts105
Category
Stirling Numbers of First Kind
Stirling numbers of the first kind count permutations by their number of cycles and connect power polynomials to rising/falling factorials.
Stirling Numbers of Second Kind
Stirling numbers of the second kind S(n,k) count how many ways to split n labeled items into k non-empty, unlabeled groups.
Primitive Roots
A primitive root modulo n is a number g that cycles through all units modulo n when you repeatedly multiply by g, so its multiplicative order equals \(\varphi(n)\).
Discrete Logarithm
The discrete logarithm problem asks for x such that g^x ≡ h (mod p) in a multiplicative group modulo a prime p.
Pollard's Rho Factorization
Pollard's Rho is a randomized algorithm that finds a non-trivial factor of a composite integer by walking a pseudorandom sequence modulo n and extracting a factor with a gcd.
Quadratic Residues
A quadratic residue modulo an odd prime p is any a for which x^2 ≡ a (mod p) has a solution; exactly half of the nonzero classes are residues.
Möbius Function and Inversion
The Möbius function μ(n) is 0 if n has a squared prime factor, otherwise it is (-1)^k where k is the number of distinct prime factors.
Divisor Function Sums
Summing the divisor function d(i) up to n equals counting lattice points under the hyperbola xy ≤ n, which can be done in O(√n) using floor-division blocks.
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.
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).
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.