In the Blog post from RP-1 we learnt how to calculate $$$\sum_{i = 0}^n {[\frac{A\cdot i + B}{C}]}$$$ in $$$\operatorname{O}(\sqrt n)$$$, then he mentioned that there is a recursive euclidean-like algorithm to calculate it in $$$\operatorname{O}(\log n)$$$. Today, as I've just been introduced to the solution by Leo_W, I would like to write it down here as an extend.

1.Theory

We define that $\operatorname{f}(n,a,b,c) = \lfloor \frac{A\cdot i + B}{C}\rfloor