$$\sum_{x=0}^{n-1} \left\lfloor \frac{ax+b}{m} \right\rfloor $$ を高速に求める。
\(a=q_1m+a’, b=q_2m+b’, 0 \leq a’,b’ < m\) とすると、
\begin{align}
\sum_{x=0}^{n-1} \left \lfloor \frac{ax+b}{m} \right\rfloor &= \sum_{x=0}^{n-1} \left(q_1x +q_2 + \left \lfloor \frac{a’x+b’}{m}\right\rfloor \right) \\
&=\frac{q_1}{2}n(n-1)+q_2n+\sum_{x=0}^{n-1} \left\lfloor \frac{a’x+b’}{m} \right\rfloor
\end{align}
となり、\(0 \leq a, b < m\) の場合に帰着できる。\(\sum_{x=0}^{n-1} \left\lfloor \frac{ax+b}{m} \right\rfloor \) は次の領域の格子点の数に等しい。
$$\begin{eqnarray}
\left\{
\begin{array}{l}
0 \leq x \leq n-1 \\
0 < y \leq \frac{a}{m}x+\frac{b}{m} \\
\end{array}
\right.
\end{eqnarray}
$$
\(x\) を \(y\) の一次関数で抑えるように式変形すると、
\begin{eqnarray}
\left\{
\begin{array}{l}
\frac{my-b}{a} \leq x \leq n-1 \\
0 < y \leq \frac{a(n-1)+b}{m} \\
\end{array}
\right.
\end{eqnarray}
となる。\(A = \left\lfloor \frac{a(n-1)+b}{m} \right\rfloor \) と置くと、この領域の格子点の数は \begin{align}
\sum_{y=1}^A \left(n – \left\lceil \frac{my-b}{a} \right\rceil \right)
=nA-\sum_{y=0}^{A-1} \left\lfloor \frac{my+mA-b+a-1}{a} \right\rfloor
\end{align} となります。最初の形に比べると \((m, a) \rightarrow (a \bmod m, a)\) と変化しています。分母が \(1\) になるまで繰り返せばよいので、計算量は \(O(\log(a)+\log(b))\) です。