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}$$$

$$$text{(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).

$$f(a,b,c,n) = nm-f(c,c)