Common Formulae — Legendre's Formula & Divisor Convolutions
Legendre’s formula, divisor and multiple convolutions in O(n log n), offline-difference batch processing for H(n)=Σf(d)g(⌊n/d⌋).
Categories
Number Theory
10 posts
Elementary Number Theory — GCD, LCM, Euler, CRT
GCD/LCM properties, Bézout/Frobenius, Euler’s theorem with power-tower reduction and φ-chain technique, congruence system merging via exGCD, CRT, and n! prime factorisation via Legendre’s formula.
Divisibility Blocking (Floor-Division Decomposition)
Divisibility blocking for O(sqrt n) floor-sum evaluation: lemma, single-variable loop, O(1) interval sum requirements, two-variable min-trick, multi-variable pseudocode, and ceiling-division blocking.
Möbius Practice — LCM Sums, Divisor-Count, Omega Numbers
Practice problems for Möbius inversion: LCMSUM, two-variable lcm sum (O(n^3/4)), FSF’s game with offline difference, divisor-count sum d(ij), Omega Numbers with Dirichlet suffix sum.
Möbius Techniques
Seven core techniques for Möbius inversion problems: loop shortening, gcd indicator expansion, coprimality reduction, Dirichlet convolution via T=dk, divisor symmetry, diagonal symmetry, and value-domain cnt[] tricks.
Multiplicative Functions, Möbius Inversion & Dirichlet Convolution
Multiplicative functions, single-point and linear-sieve evaluation; Möbius function, both forms of Möbius inversion with full derivations and examples; Dirichlet convolution, key identities, Du Jiao sieve; generalized Möbius …
From Eratosthenes to Möbius Inclusion-Exclusion
Eratosthenes sieve for μ; g/f/h framework; Conclusions 1 and 2 with derivations and tables; GCD table intuition; CF 803F Coprime Subsequences with bottom-up and Möbius approaches.
Sieve Problems — Coin System DP via Sieve
Greedy optimality for divisibility-chain coin systems, DP over the maximum denomination, and a sieve-style transition by adding one larger coin.
Min_25 Sieve and Du Jiao Sieve
Min_25 sieve: theory, two complete examples, Lagrange interpolation for power sums. Du Jiao sieve: template, P3768, GCD sum, LCM sum.
Primality, Factorisation & Residues (Miller-Rabin, Pollard Rho, Tonelli-Shanks)
Miller-Rabin primality test, Pollard Rho factorisation, Tonelli-Shanks for quadratic residues, cubic residues via F_p[t]/(t^3-a), quartic residues by double square root, and general k-th residues via primitive root + BSGS, plus …