The floor sum is an algorithm that solves for the value of a function approximating $$$f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor$$$ in $$$O(\log n)$$$ time complexity.

Maybe you haven't heard of it, but you can get the algorithm by simple mathematical derivation.

To calculate the sum of the functions, $$$n \le 10^{9}$$$

(I) when $$$a \lt c$$$ and $$$b \lt c$$$.

First simplify $$$f(a,b,c,n)$$$.

$

Let $$$m = \frac{an+b}{c}\rfloor$$$, then we have: $$$f(a,b,c) = (frac{an+b}{c}\rfloor-1)$$$.