おことわり

この記事は厳密性を保証しません。

Floor Sum とは？

$\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor$ を高速に求めるやつ(ただし $N,M,A,B\in \mathbb{Z}$ で $N,A,B \geq 0$ ， $M \gt 0$ )。

どういうアルゴリズムを使えばいいのか

まず， $A = Q_A M+A'$ ， $B = Q_B M+B'$ として $0 \leq A' \lt M$ ， $0 \leq B' \lt M$ の状態を作り上げます。すると

$\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor$

$\displaystyle = \sum_{i=0}^{N-1} \lfloor \dfrac{Q_A M+A'+(Q_B M+B')i}{M} \rfloor$

$\displaystyle = \sum_{i=0}^{N-1} \left( Q_A + Q_B i + \lfloor \dfrac{A'+B'i}{M} \rfloor \right)$

$\displaystyle =\sum_{i=0}^{N-1} Q_A + \sum_{i=0}^{N-1} Q_B i + \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor$

$\displaystyle = N Q_A + \dfrac{N(N-1)}{2} Q_B + \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor$

となります。 $N Q_A$ と $\dfrac{N(N-1)}{2} Q_B$ は簡単に求められるので， $\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor$ の部分をうまく求めればいいです。

$B'=0$ のときは当然 $N \lfloor \dfrac{A'}{M} \rfloor = 0$ となる*1ので，以下では $B'\neq 0$ の場合について考えます。

ここで， $\lfloor \dfrac{A'+B'i}{M} \rfloor \geq j$ となるような $i$ の個数を $j$ ごとに数え上げることを考えます。

$j$ は整数なので， $\lfloor \dfrac{A'+B'i}{M} \rfloor \geq j$ と $\dfrac{A'+B'i}{M} \geq j$ は同値であり，

$j \leq \dfrac{A'+B'i}{M}$

$\iff{} Mj \leq A'+B'i$

$\iff{} Mj-A' \leq B'i$

$\iff{} \dfrac{Mj-A'}{B'} \leq i$

$\iff{} \lceil \dfrac{Mj-A'}{B'} \rceil \leq i$

$\iff{} \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor \leq i$

よって $\lfloor \dfrac{A'+B'i}{M} \rfloor \geq j$ となるような $i$ の個数は $N - \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor$ 個あります。

これを $1$ から $N' = \lfloor \dfrac{A'+B'(N-1)}{M} \rfloor$ まで足し合わせて

$\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor$ $\displaystyle = \sum_{j=1}^{N'} \left( N - \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor \right)$ $\displaystyle = \sum_{j=1}^{N'} N - \sum_{j=1}^{N'} \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor$

となります。ここで， $j' = j - 1$ という記号を導入すると

$\displaystyle N'N - \sum_{j'=0}^{N'-1} \lfloor \dfrac{Mj'+M-A'+B'-1}{B'} \rfloor$

となります。

つまり，結局のところ

$\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor$

$\displaystyle = N Q_A + \dfrac{N(N-1)}{2} Q_B + N'N - \sum_{j'=0}^{N'-1} \lfloor \dfrac{Mj'+M-A'+B'-1}{B'} \rfloor$

となります。ここで， $\displaystyle \sum_{j'=0}^{N'-1} \lfloor \dfrac{Mj'+M-A'+B'-1}{B'} \rfloor$

の部分は元の問題と同じ構造をしているので再帰的に解けば問題が解けます。

再帰関数を作る

$\displaystyle f(N,M,A,B) = \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor$ とおきます。

するとさっきの式は

$\displaystyle f(N,M,A,B) = N Q_A + \dfrac{N(N-1)}{2} Q_B + N'N - f(N',B',M-A'+B'-1,M)$

と書き直せます。

計算量

雑に見積もります。

$\displaystyle f(\cdot,M,\cdot,B)$ は $\displaystyle f(\cdot ,B\% M,\cdot,M)$ を呼び出すので，だいたいユークリッドの互除法と同じくらいの計算量になることが分かります。よって，計算量は $O(\log(B+M))$ で抑えられそうだということが分かります。