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 = \left\lfloor\frac{an+b}{c}\right\rfloor$$$, then we get:

For the above derivation, we call it ‘**Lemma 1**’:

Lemma 1:

Next consider the simplification of $$$h(a,b,c,n)$$$, which follows from ‘**Lemma 1**’:

Let $$$t = \lfloor\frac{cj+c-b-1}{a}\rfloor, m = \lfloor\frac{an+b}{c}\rfloor$$$, we have: