Concepts4
βMathAdvanced
Floor Sum Formula
The floor sum computes S(n,m,a,b) = sum_{i=0}^{n-1} floor((a i + b)/m) efficiently in O(log(min(a,m))) time.
#floor sum#atcoder library#euclidean algorithm+12
βMathAdvanced
Discrete Logarithm
The discrete logarithm problem asks for x such that g^x β‘ h (mod p) in a multiplicative group modulo a prime p.
#discrete logarithm#baby-step giant-step#pollard rho dlp+12
βMathAdvanced
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.
#quadratic residues#legendre symbol#euler criterion+12
βMathAdvanced
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.
#mobius function#mobius inversion#dirichlet convolution+12