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)$$$.
f(a,b,c,n)&=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\
&=\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\
&=\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[j+1\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c\le{ai+b}\bigg]\\
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c-b\le{ai}\bigg]\\
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c-b - 1 \lt {ai}\bigg]\\
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor \lt i\bigg]\\
&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n\bigg[\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor \lt i\bigg]\\
&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b - 1}{a}\rfloor+1}^n1\\
&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg(n-\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor\bigg)\\
&=n\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor\\
&=n\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-f(c,c+b-1,a,\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-1)\\
\end{aligned}$$$
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)
