Groups
Category
Level
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.
An ordinary generating function (OGF) encodes a sequence (a_n) as a formal power series A(x) = \sum_{n \ge 0} a_n x^n.
Berlekamp–Massey (BM) finds the shortest linear recurrence that exactly fits a given sequence over a field (e.g., modulo a prime).
A linear recurrence defines each term as a fixed linear combination of a small, fixed number of previous terms.