### pinkPanties's blog

By pinkPanties, history, 2 years ago,

Hi all, i was going through this question about floor sum on atcoder.

Can anyone explain me how to approach this without library ?

Question

Thanks for explaining :)

• 0

| Write comment?
 » 2 years ago, # |   0 I hope this helps you Generalized floor Sum of A.P
•  » » 2 years ago, # ^ |   +5 thanks :)
 » 2 years ago, # |   +16 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.
•  » » 2 years ago, # ^ |   +5 Thanks, elegant explanation :)
•  » » 4 months ago, # ^ |   0 A small correction: \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-1}{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-1}{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-1\right) \end{align}