はじめに
この記事では、floor sum を計算する漸化式の導出方法を紹介します。
floor sum は、次の形の和を計算量 $O(\log M)$ で計算するアルゴリズムです。
$$f(N, M, A, B) = \sum_{k=0}^{N-1} \left\lfloor \frac{Ak + B}{M} \right\rfloor$$
ここで、$N$ は $0$ 以上の整数、$M$ は正の整数、$A, B$ は整数とします。
floor sum の導出を扱う記事はすでにいくつかありますが、本記事の特徴は以下の通りです。
- 指示関数を使い、ある程度機械的に導出した
- 床関数 = i ではなく 床関数 > iとして主客転倒した
- 導出の行間を比較的狭くしつつ、全体像も見えるようにした
漸化式とソースコード
まずは、floor sum を計算する漸化式とそのソースコードを紹介します。
$N = 0$ のときは $f(N, M, A, B) = 0$ です。 以下、$N > 0$ とします。
$A$ を $M$ で割った商と余りを、それぞれ $A_q, A_r$ とします。 また、$B$ を $M$ で割った商と余りを、それぞれ $B_q, B_r$ とします。
-
$A_r = 0$ のとき
以下が成り立ちます。
$$f(N, M, A, B) = \frac{N(N-1)}{2}A_q + NB_q$$
-
$A_r \neq 0$ のとき
$Y = \left\lfloor \dfrac{A_r (N-1) + B_r}{M} \right\rfloor$ とすると、以下が成り立ちます。
$$ \begin{aligned} &f(N, M, A, B) = \frac{N(N-1)}{2}A_q + NB_q\\ &\phantom{f(N, M, A, B) = {}} + NY - f(Y, A_r, M, M - B_r + A_r - 1) \end{aligned} $$
1 回再帰すると $(M, A)$ が $(A \bmod M, M)$ になります。これはユークリッドの互除法と同じノリで小さくなり、再帰の呼び出し回数は $O(\log M)$ 回になります。
Rust で floor sum を実装すると、以下のようになります。
fn floor_sum(n: i64, m: i64, a: i64, b: i64) -> i64 { if n == 0 { return 0; } let aq = i64::div_euclid(a, m); let ar = i64::rem_euclid(a, m); let bq = i64::div_euclid(b, m); let br = i64::rem_euclid(b, m); let term1 = aq * n * (n - 1) / 2 + bq * n; let term2 = { if ar == 0 { 0 } else { let y = i64::div_euclid(ar * (n - 1) + br, m); n * y - floor_sum(y, ar, m, m - br + ar - 1) } }; term1 + term2 }
floor sum を導出するための道具
floor sum を導出するための道具を説明します。
まずは、この記事で使う記法を説明します。
- この記事では、$0$ を自然数に含めます。
- $[0, n) := \{x \in \mathbb{Z} \mid 0 \leq x < n\}$
- 集合 $A$ に対して、$\# A$ を $A$ の要素数とします。
- $\mathbb{1}[P]$ を命題 $P$ の指示関数とします。$P$ が成り立つとき $1$、成り立たないとき $0$ です。
後で集合の要素数を指示関数の和に書き換えるため、まず次の性質を紹介します。
有限集合 $X$ の部分集合 $A$ に対して、以下が成り立ちます。
$$\# A = \sum_{a \in X} \mathbb{1}[a \in A]$$
floor sum の漸化式の導出で大事になる主客転倒を紹介します。
$X, Y$ を有限集合とし、$R$ を $X \times Y$ の部分集合とします。すなわち、$R$ は $X$ と $Y$ の間の二項関係です。
「各 $x \in X$ ごとに、対応する $y \in Y$ の数を数える」という数え方を、「各 $y \in Y$ ごとに、対応する $x \in X$ の数を数える」という数え方に切り替えると、うまくいくことがあります。このような考え方を主客転倒（または double counting）と呼びます。
式で書くと、以下のようになります。
$$ \begin{align*} \sum_{x \in X} \# \{y \in Y \mid (x, y) \in R\} &= \sum_{x \in X} \sum_{y \in Y} \mathbb{1}[(x, y) \in R]\\ &= \sum_{y \in Y} \sum_{x \in X} \mathbb{1}[(x, y) \in R]\\ &= \sum_{y \in Y} \# \{x \in X \mid (x, y) \in R\} \end{align*} $$
なお、左辺と右辺はどちらも $R$ に属する組 $(x, y)$ の個数を数えています。
この記事では、上記の式変形のように、集合の要素数を指示関数の和で表してから、2つの総和を入れ替えることで主客転倒を行います。こうすると、主客転倒を強く意識せずとも、機械的な式変形として扱えます。
さらに、主客転倒の準備と床関数・天井関数の式変形に使う性質を3つ紹介します。命題2は主客転倒の準備に使い、命題3と4は床関数・天井関数の式変形に使います。
$N$ 以下の自然数 $a$ に対して、以下が成り立ちます。
$$a = \# [0, a) = \sum_{y=0}^{N-1} \mathbb{1}[y < a]$$
floor sum の導出では、自然数を $\# [0, a)$ のような集合の要素数として表すことが鍵になります。この記事では、この集合の要素数を指示関数の和で表し、主客転倒を機械的にできるようにしています。
整数 $n$ と実数 $x$ に対して、以下が成り立ちます。
$$n \leq x \iff n \leq \lfloor x \rfloor$$
$$x \leq n \iff \lceil x \rceil \leq n$$
各同値の左側は実数の世界での比較、右側は整数の世界での比較になっています。この性質は、「左側の実数の世界での比較」と「右側の整数の世界での比較」が行き来できることを表しています。
整数 $a$ と正の整数 $b$ に対して、以下が成り立ちます。
$$\left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a + b - 1}{b} \right\rfloor$$
floor sum の導出
まず、$A$ と $B$ を $M$ で割ります。商に由来する項は床関数の外へ出せるので、余りの部分だけが残ります。残った部分には主客転倒を使うことでさらに割り進めることができます。
$A, B$ の商と余りを考える
$A$ を $M$ で割った商と余りを、それぞれ $A_q, A_r$ とします。 また、$B$ を $M$ で割った商と余りを、それぞれ $B_q, B_r$ とします。 つまり、以下が成り立ちます。
$$ \begin{aligned} A &= A_q M + A_r \quad (0 \leq A_r < M)\\ B &=B_q M + B_r \quad (0 \leq B_r < M) \end{aligned} $$
商と余りを使うと、$f(N, M, A, B)$ は以下のように式変形できます。
$$ \begin{align} f(N, M, A, B) &= \sum_{k=0}^{N-1} \left\lfloor \frac{Ak + B}{M} \right\rfloor\\ &= \sum_{k=0}^{N-1} \left\lfloor \frac{(A_qM + A_r)k + (B_qM + B_r)}{M} \right\rfloor\\ &= \sum_{k=0}^{N-1} \left\lfloor A_qk + B_q + \frac{A_rk + B_r}{M} \right\rfloor\\ &= \sum_{k=0}^{N-1} \left( A_qk + B_q + \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right)\\ &= \frac{N(N-1)}{2}A_q + NB_q + \sum_{k=0}^{N-1}\left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \end{align} $$
最後に、以下の部分を処理すればよいです。
$$\sum_{k=0}^{N-1}\left\lfloor \frac{A_rk + B_r}{M} \right\rfloor$$
$A_r = 0$ の場合
$A_r = 0$ のときは、$0 \leq B_r < M$ なので各 $k$ に対して以下が成り立ちます。
$$\left\lfloor \frac{A_rk + B_r}{M} \right\rfloor = \left\lfloor \frac{B_r}{M} \right\rfloor = 0$$
したがって、以下が成り立ちます。
$$f(N, M, A, B) = \frac{N(N-1)}{2}A_q + NB_q$$
$A_r \neq 0$ の場合
まず、$0 \leq k < N$ における次の床関数の最大値を考えます。
$$\left\lfloor \frac{A_rk + B_r}{M} \right\rfloor$$
$0 \leq A_r < M$ かつ $A_r \neq 0$ なので $A_r> 0$ です。したがって、これは $k = N-1$ のときに最大になります。
その最大値を $Y$ とおきます。
$$Y := \left\lfloor \dfrac{A_r(N-1) + B_r}{M} \right\rfloor$$
以下のように式変形します。
$$ \begin{aligned} &\sum_{k=0}^{N-1}\left\lfloor \frac{A_rk + B_r}{M} \right\rfloor && \text{(1)}\\ ={}& \sum_{k=0}^{N-1}\# \left[0, \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right) && \text{(2)}\\ ={}& \sum_{k=0}^{N-1} \sum_{y=0}^{Y-1} \mathbb{1}\left[y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right] && \text{(3)}\\={}& \sum_{y=0}^{Y-1} \sum_{k=0}^{N-1} \mathbb{1}\left[y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right] && \text{(4)}\\={}& \sum_{y=0}^{Y-1} \sum_{k=0}^{N-1} \mathbb{1}\left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \leq k\right] && \text{(5)}\\={}& \sum_{y=0}^{Y-1} \# \left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right) && \text{(6)}\\={}& NY - \sum_{y=0}^{Y-1}\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor && \text{(7)}\\={}& NY - f(Y, A_r, M, M - B_r + A_r - 1) && \text{(8)} \end{aligned} $$
$(1) = (2)$ の導出
示したいこと
$$ \begin{aligned} &\sum_{k=0}^{N-1}\left\lfloor \frac{A_rk + B_r}{M} \right\rfloor && \text{(1)}\\ ={}&\sum_{k=0}^{N-1}\# \left[0, \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right) && \text{(2)} \end{aligned} $$
$0 \leq k < N$ を満たす $k$ を固定します。$0 \leq A_r < M$ かつ $0 \leq B_r < M$ なので、$\dfrac{A_rk + B_r}{M} \geq 0$ が成り立ちます。
したがって、$\left\lfloor \dfrac{A_rk + B_r}{M} \right\rfloor \geq 0$ です。よって、$\left\lfloor \dfrac{A_rk + B_r}{M} \right\rfloor$ は区間 $\left[0, \left\lfloor \dfrac{A_rk + B_r}{M} \right\rfloor\right)$ の要素数です。
これは命題2の前半部分です。
$(2) = (3)$ の導出
示したいこと
$$ \begin{aligned} &\sum_{k=0}^{N-1}\# \left[0, \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right) && \text{(2)}\\ ={}&\sum_{k=0}^{N-1} \sum_{y=0}^{Y-1} \mathbb{1}\left[y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right] && \text{(3)} \end{aligned} $$
$0 \leq k < N$ を満たす $k$ を固定します。$\left\lfloor \dfrac{A_rk + B_r}{M} \right\rfloor \leq Y$ が成り立ちます。
$0 \leq y < Y$ の範囲では、指示関数 $\mathbb{1}\left[y < \left\lfloor \dfrac{A_rk + B_r}{M} \right\rfloor\right]$ は、$y$ が区間 $\left[0, \left\lfloor \dfrac{A_rk + B_r}{M} \right\rfloor\right)$ に属するときに $1$、それ以外のときに $0$ です。したがって、以下が成り立ちます。
$$\# \left[0, \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right) = \sum_{y=0}^{Y-1} \mathbb{1}\left[y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right]$$
これは命題2の後半部分です。
$(3) = (4)$ の導出
示したいこと
$$ \begin{aligned} &\sum_{k=0}^{N-1} \sum_{y=0}^{Y-1} \mathbb{1}\left[y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right] && \text{(3)}\\={}&\sum_{y=0}^{Y-1} \sum_{k=0}^{N-1} \mathbb{1}\left[y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right] && \text{(4)} \end{aligned} $$
和の順番を入れ替えます。
$(4) = (5)$ の導出
示したいこと
$$ \begin{aligned} &\sum_{y=0}^{Y-1} \sum_{k=0}^{N-1} \mathbb{1}\left[y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor \right] && \text{(4)}\\={}&\sum_{y=0}^{Y-1} \sum_{k=0}^{N-1} \mathbb{1}\left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \leq k\right] && \text{(5)} \end{aligned} $$
指示関数の内側の条件を $k$ に関する条件に直します。
$$ \begin{align} y < \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor &\iff y + 1 \leq \left\lfloor \frac{A_rk + B_r}{M} \right\rfloor\\ &\iff y + 1 \leq \frac{A_rk + B_r}{M}\qquad \text{(命題3)}\\ &\iff My + M \leq A_rk + B_r\\ &\iff My + M - B_r \leq A_rk\\ &\iff \frac{My + M - B_r}{A_r} \leq k\\ &\iff \left\lceil \frac{My + M - B_r}{A_r} \right\rceil \leq k\qquad \text{(命題3)}\\ &\iff \left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \leq k\qquad \text{(命題4)} \end{align} $$
$(5) = (6)$ の導出
示したいこと
$$ \begin{aligned} &\sum_{y=0}^{Y-1} \sum_{k=0}^{N-1} \mathbb{1}\left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \leq k\right] && \text{(5)}\\ ={}&\sum_{y=0}^{Y-1} \# \left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right) && \text{(6)} \end{aligned} $$
$0 \leq y \leq Y-1$ を満たす $y$ を固定します。$0 \leq y$、$0 \leq B_r < M$、$A_r> 0$ なので、以下が成り立ちます。
$$\frac{My + M - B_r + A_r - 1}{A_r} \geq 0$$
したがって、以下が成り立ちます。
$$\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \geq 0$$
$0 \leq k < N$ のとき、指示関数 $\mathbb{1}\left[\left\lfloor \dfrac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \leq k\right]$ は、$k$ が区間 $\left[\left\lfloor \dfrac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right)$ に属するときに $1$、それ以外のときに $0$ です。したがって、以下が成り立ちます。
$$\sum_{k=0}^{N-1} \mathbb{1}\left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \leq k\right] = \# \left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right)$$
$(6) = (7)$ の導出
示したいこと
$$ \begin{aligned} &\sum_{y=0}^{Y-1} \# \left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right) && \text{(6)}\\ ={}&NY - \sum_{y=0}^{Y-1}\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor && \text{(7)} \end{aligned} $$
$0 \leq y \leq Y-1$ を満たす各 $y$ に対して、区間 $\left[\left\lfloor \dfrac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right)$ がねじれていないこと、つまり、区間の左端が $N-1$ 以下であることを確認します。
$y < Y$ なので、$Y$ の定義から以下が成り立ちます。
$$y < \left\lfloor \frac{A_r(N-1) + B_r}{M} \right\rfloor$$
これは、$(4) = (5)$ の導出で使う同値変形に $k = N-1$ を代入したときの左辺です。したがって、以下が成り立ちます。
$$\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \leq N-1$$
半開区間の要素数は右端から左端を引いた値です。したがって、以下が成り立ちます。
$$\# \left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right) = N - \left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor$$
つまり、以下が成り立ちます。
$$ \begin{aligned} &\sum_{y=0}^{Y-1} \# \left[\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor, N\right)\\ ={}&\sum_{y=0}^{Y-1} \left(N - \left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor\right)\\ ={}&NY - \sum_{y=0}^{Y-1}\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor \end{aligned} $$
$(7) = (8)$ の導出
示したいこと
$$ \begin{aligned} &NY - \sum_{y=0}^{Y-1}\left\lfloor \frac{My + M - B_r + A_r - 1}{A_r} \right\rfloor && \text{(7)}\\ ={}&NY - f(Y, A_r, M, M - B_r + A_r - 1) && \text{(8)} \end{aligned} $$
最後の和は、$f(N, M, A, B) = \displaystyle \sum_{k=0}^{N-1}\left\lfloor \dfrac{Ak + B}{M} \right\rfloor$ という定義から従います。
$(2)$ から $(6)$ にかけて、主客転倒を行っていると言えます。
以上をまとめると、$A_r \neq 0$ のとき以下が得られます。
$$f(N, M, A, B) = \frac{N(N-1)}{2}A_q + NB_q + NY - f(Y, A_r, M, M - B_r + A_r - 1)$$
証明の振り返り
ここまでで floor sum の漸化式を導出しました。最後に、導出の途中で使った考え方を振り返ります。
床関数と不等号
床関数は、$n \leq \lfloor x\rfloor \iff n \leq x$（$n$ は整数、$x$ は実数）という性質があるため、不等号と相性がよいです。
floor sum の導出で主客転倒をするときは、以下の2つの方法があります。
- 各 $y$ に対して、$\left\lfloor \dfrac{A_rk+B_r}{M} \right\rfloor=y$ となる $k$ の個数を数える。
- 各 $y$ に対して、$\left\lfloor \dfrac{A_rk+B_r}{M} \right\rfloor>y$ となる $k$ の個数を数える。
今回は、床関数が不等号と相性がよいため後者を選びました。
$\left\lfloor \dfrac{A_rk+B_r}{M} \right\rfloor>y$ となる $k$ の個数を数える後者の方法では、$n \leq \lfloor x\rfloor \iff n \leq x$ という性質を使って、以下のようにシンプルな同値変形ができました。（$(4) = (5)$ の導出の部分です。）
$$ \begin{aligned} & y < \left\lfloor \frac{A_rk+B_r}{M} \right\rfloor\\ \iff{}& y+1 \leq \left\lfloor \frac{A_rk+B_r}{M} \right\rfloor\\ \iff{}& y+1 \leq \frac{A_rk+B_r}{M} \end{aligned} $$
前者の床関数を等号で扱う方法でも導出できます。 床関数を等号で扱うと、$\left\lfloor x \right\rfloor = n \iff n \leq x < n + 1$（$n$ は整数、$x$ は実数）という同値関係を使うことになります。 同値関係の右辺では二つの不等式を扱うため、不等号を使う今回の方法と比べるとわずかに複雑な可能性があります（あまり変わらない可能性もあります）。
参考: 床関数を等号で扱う方法の導出
$A_r > 0$ とします。各 $y$ に対して、$\left\lfloor \dfrac{A_rk+B_r}{M} \right\rfloor=y$ となる $k$ の個数を数えます。
$$ \begin{aligned} \left\lfloor \frac{A_rk+B_r}{M} \right\rfloor=y &\iff y \leq \frac{A_rk+B_r}{M} < y+1\\ &\iff \frac{My-B_r}{A_r} \leq k < \frac{M(y+1)-B_r}{A_r}\\ &\iff \left\lceil \frac{My-B_r}{A_r} \right\rceil \leq k < \left\lceil \frac{M(y+1)-B_r}{A_r} \right\rceil \end{aligned} $$
したがって、$\left\lfloor \dfrac{A_rk+B_r}{M} \right\rfloor=y$ となる $0 \leq k < N$ の個数は、次の集合の要素数です。
$$ \left[ \left\lceil\frac{My-B_r}{A_r}\right\rceil, \left\lceil\frac{M(y+1)-B_r}{A_r}\right\rceil \right) \cap [0,N) $$
この集合を分かりやすくするため、$C_y$ を次のようにおきます。
$$ C_y = \begin{cases} 0 & (y=0)\\ \left\lceil \dfrac{My-B_r}{A_r} \right\rceil & (1 \leq y \leq Y)\\ N & (y=Y+1) \end{cases} $$
$0 \leq y \leq Y$ のとき、以下が成り立ちます。
$$ \left[ \left\lceil\frac{My-B_r}{A_r}\right\rceil, \left\lceil\frac{M(y+1)-B_r}{A_r}\right\rceil \right) \cap [0,N) = [C_y,C_{y+1}) $$
よって、$f(N, M, A_r, B_r)$ は次のように表せます。
$$f(N,M,A_r,B_r) = \sum_{y=0}^{Y} y \# [C_y,C_{y+1})$$
半開区間の要素数は右端から左端を引いた値です。したがって、以下が成り立ちます。
$$ \begin{aligned} f(N,M,A_r,B_r) &= \sum_{y=0}^{Y} y(C_{y+1}-C_y)\\ &= NY - \sum_{y=1}^{Y} C_y\\ &= NY - \sum_{y=1}^{Y}\left\lceil \frac{My-B_r}{A_r} \right\rceil\\ &= NY - \sum_{y=0}^{Y-1}\left\lfloor \frac{My+M-B_r+A_r-1}{A_r} \right\rfloor\\ &= NY - f(Y,A_r,M,M-B_r+A_r-1) \end{aligned} $$
自然数を指示関数の和で表す
floor sum の導出では、自然数 $a$ を $a=\displaystyle\sum_{i=0}^{a-1}\mathbb{1}[i < a]$ のように指示関数の和で表す考え方を使いました。指示関数を使うと、主客転倒を強く意識しなくても、総和の交換を含む機械的な式変形として導出できます。
自然数を指示関数の和で表すテクニックは floor sum の導出以外にも使えます。例えば、$X$ が $0$ 以上 $L$ 以下の整数を値に取る確率変数であるときに成り立つ有名な式 $\displaystyle\mathbb{E}[X]=\sum_{i=0}^{L-1}\Pr(i < X)$ の導出にも使えます。実際に導出します。
$X$ より小さい $0$ 以上の整数の個数は $X$ です。これを、指示関数を使って $X=\displaystyle\sum_{i=0}^{L-1}\mathbb{1}[i < X]$ と表します。
floor sum の導出で総和を交換したのと同じように、ここでは期待値と総和を交換します。命題 $P$ に対して成り立つ $\mathbb{E}[\mathbb{1}[P]] = \Pr(P)$ を使うと、以下のように式変形できます。
$$ \begin{aligned} \mathbb{E}[X] &= \mathbb{E}\left[\sum_{i=0}^{L-1}\mathbb{1}[i < X]\right]\\ &= \sum_{i=0}^{L-1}\mathbb{E}\left[\mathbb{1}[i < X]\right]\\ &= \sum_{i=0}^{L-1}\Pr(i < X) \end{aligned} $$
主客転倒とユークリッドの互除法
floor sum の導出でなぜ主客転倒をしたらうまくいったのかを考えます。 結論から言うと、主客転倒することで、係数と法の役割が交換され、再び余りが取れるようになり、係数と法をさらに小さくできるようになったと説明できます。
主客転倒で何が起きたのかを見るため、導出の概要を振り返ります。 導出の最初に、$A$ を $M$ で割ったときの余り $A_r$ を考えることで、係数を $A$ から $A_r$ へ小さくできました。 次に主客転倒を行うことで、次の形の再帰呼び出しが得られました。 $$f(Y,A_r,M,M-B_r+A_r-1)$$
主客転倒で係数と法が交換され、再び係数 $M$ を法 $A_r$ で割った余り $M\bmod A_r$ が考えられるようになりました。 このように、floor sum の導出では、余りを考えることと主客転倒を繰り返すことで、余りを小さくしていくことができました。
この構造は、ユークリッドの互除法でも現れます。 ユークリッドの互除法では、$\gcd(a,b)$ が $a$ を $b$ で割った余りに置き換えても変わらない性質、つまり $\gcd(a,b)=\gcd(a\bmod b,b)$ が鍵になっています。 また、$a\bmod b$ と $b$ は交換することで、さらに割り進める（$b$ を $a\bmod b$ で割る）ことができます。割り進めることで、次の再帰では法が $a\bmod b$ から $b\bmod(a\bmod b)$ へとどんどん小さくできます。
以上のように、割られる数と割る数を交換して余りを考えることを繰り返すことで、floor sum でもユークリッドの互除法でも、余りを小さくすることができたと言えます。 割られる数と割る数を交換するには、ユークリッドの互除法では $\gcd$ の可換性を使えばよく、floor sum の導出では主客転倒を使えばよいという話になります。 これが floor sum の導出における主客転倒の立ち位置とも言えます。
図で見る主客転倒
$A=3$、$M=5$、$B=2$、$N=13$ としたときの $\displaystyle\sum_{k=0}^{N-1}\left\lfloor \frac{Ak+B}{M} \right\rfloor$ を図にすると、以下の図の青丸の格子点の数になります。
主客転倒で数え方がどう変わるかを見ます。
図の黒線は $y=\dfrac{Ak+B}{M}$ を表します。青い階段状の領域は、$0 \leq k < N$ かつ $y \in \left[0, \left\lfloor \dfrac{Ak+B}{M} \right\rfloor\right)$ となる $(k, y)$ を実数の領域として可視化したものです。
その格子点の数が $\displaystyle\sum_{k=0}^{N-1}\left\lfloor \dfrac{Ak+B}{M} \right\rfloor$ を表しています。 これは、各整数 $k$ に対応する列の格子点の数、すなわち $y \in \left[0, \left\lfloor \dfrac{Ak+B}{M} \right\rfloor\right)$ を満たす整数 $y$ の個数が $\left\lfloor \dfrac{Ak+B}{M} \right\rfloor$ であるからです。
今回の導出では、主客転倒をすることで $\displaystyle\sum_{y=0}^{Y-1}\# \left[\left\lfloor \dfrac{My+M-B_r+A_r-1}{A_r} \right\rfloor, N\right)$ という式が現れました。これは、各 $y$ に対して $k \in \left[\left\lfloor \dfrac{My+M-B_r+A_r-1}{A_r} \right\rfloor, N\right)$ を満たす $k$ の個数を足し合わせたものと言えます。図では、青い格子点を行ごとに数えることに対応しています。
つまり、今回の主客転倒は、列ごとに数えていた青い格子点を、行ごとに数え直したものだと言えます。図で表すと以下のようになります。
導出中の余りを取る部分を含めたより詳しい可視化は、視覚的に理解するfloor sum | 東京科学大学デジタル創作同好会traP をご覧ください。
おわりに
この記事では、floor sum の導出を行い、導出で出てきた考え方を整理しました。
floor sum の導出は、主客転倒や床関数・天井関数の扱いの練習になるのでおすすめです。「$A$ と $B$ に対して $M$ で割った余りを考える」と「主客転倒をする」という2つのエッセンスさえ知っていれば、特殊な発想を使わずに自然な操作で導出できると思います。
とくに床関数・天井関数を使った式変形は、ABC443 G - Another Mod of Linear Problem のような floor sum を使う問題を考察するときにも役立ちます。
