I hope this helps you

Generalized floor Sum of A.P

Let

$$$\begin{align} f(n, m, a, b) = \sum _ {i = 0} ^ {n - 1} \left \lfloor \frac{a\cdot i + b}{m} \right \rfloor \end{align}$$$.

If $$$a \ge m$$$, the following reduces $$$a$$$ to equal or less than the half.

$$$\begin{align} f(n,m,a,b) &= \sum _ {i = 0} ^ {n - 1} \left \lfloor \frac{a\cdot i + b}{m} \right \rfloor \newline &= \sum _ {i = 0} ^ {n - 1} \left\lfloor \frac{ \left( \left \lfloor \frac{a}{m} \right\rfloor \cdot m + a \% m \right) \cdot i + b}{m} \right \rfloor \newline &= \sum _ {i = 0} ^ {n - 1} \left( \left\lfloor \frac{a}{m} \right\rfloor \cdot i + \frac{ a \% m \cdot i + b }{m} \right) \newline &= \left\lfloor \frac{a}m \right\rfloor \cdot \frac{(n-1) \cdot n}2 + f(n, m, a \% m, b) \end{align}$$$

Similarly, if $$$b \ge m$$$,

$$$\begin{align} f(n,m,a,b) = \left\lfloor \frac{b}m \right\rfloor \cdot n + f(n,m,a,b \% m) \end{align}$$$

Now we may assume $$$a, b < m$$$. There's a general technique of changing variables in summation. We denote, for a proposition $$$p$$$, $$$[p] = 1$$$ if $$$p$$$ is $$$\mathrm{true}$$$, otherwise $$$[p] = 0$$$.

$$$\begin{align} f(n,m,a,b) &= \sum _ {i = 0} ^ {n - 1} \left \lfloor \frac{a\cdot i + b}{m} \right \rfloor \newline &= \sum _ {i = 0} ^ {n - 1} \sum _ {j = 0} ^ {\left\lfloor \frac{a \cdot (n - 1) + b}m \right\rfloor - 1} \left[ j < \left\lfloor \frac{a \cdot i + b}m \right\rfloor \right] \newline &= \sum _ {j = 0} ^ {\left\lfloor \frac{a \cdot (n - 1) + b}m \right\rfloor - 1} \sum _ {i = 0} ^ {n - 1} \left[ j < \left\lfloor \frac{a \cdot i + b}m \right\rfloor \right] \newline &= \sum _ {j = 0} ^ {\left\lfloor \frac{a \cdot (n - 1) + b}m \right\rfloor - 1} \sum _ {i = 0} ^ {n - 1} \left[ m \cdot (j + 1) \le a \cdot i + b \right] \newline &= \sum _ {j = 0} ^ {\left\lfloor \frac{a \cdot (n - 1) + b}m \right\rfloor - 1} \sum _ {i = 0} ^ {n - 1} \left[ \left\lfloor \frac{m \cdot j + m - b}{a} \right\rfloor < i \right] \newline &= \sum _ {j = 0} ^ {\left\lfloor \frac{a \cdot (n - 1) + b}m \right\rfloor - 1} \left( n - 1 - \left\lfloor \frac{m \cdot j + m - b}{a} \right\rfloor \right) \newline &= (n - 1) \cdot \left\lfloor \frac{a \cdot (n - 1) + b}m \right\rfloor - f\left(\left\lfloor \frac{a \cdot (n - 1) + b}m \right\rfloor, a, m, m - b\right) \end{align}$$$

Notice that $$$m$$$ and $$$a$$$ switched their position. So in each iterations, $$$a$$$ gets halved, then $$$a$$$ and $$$m$$$ switch position. This yields $$$O(\log \min(m, a))$$$ complexity.