Sums of the form $$\sum_{i=1}^n \left\lfloor \frac{pi+q}{r} \right\rfloor$$ can be evaluated in $O(\log n)$ time. See Summation of Floor Function Series for a special case.

Problems

• It's a Mod, Mod, Mod, Mod World

External links

• Summation of Floor Function Series
• Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, Chapter 3.5, Floor/Ceiling Sums.