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 on codeforces blogs.
1.Theory
We define that $$$\operatorname{f}(n,a,b,c) = \lfloor \frac{A\cdot i + B}{C}\rfloor$$$, we found that:
\operatorname{f}(n,a,b,c) &= \lfloor \frac{A\cdot i + B}{C}\rfloor\\ &= \sum_{i = 1}^n \sum_{j = 1}^{\infty} [\lfloor \frac{A\cdot i + B}{C}\rfloor \ge j]\\ &= \sum_{j = 1}^{\infty} \sum_{i = 1}^n [\lfloor \frac{A\cdot i + B}{C}\rfloor \ge j] \end{aligned} $$$
