床関数・天井関数（floor function / ceiling function）の典型まとめ

考察をショートカットしたいので書きました。負の数が絡むと頭が壊れがち。

見つけ次第追加していこうと思います。

定義

床関数

$ x \in \mathbb{R} $ 以下の最大の整数を $ \lfloor x \rfloor $ で表し、$ \lfloor \cdot \rfloor $ を床関数（floor function）と呼びます。

例：$ \lfloor 1.2 \rfloor = 1$、$ \lfloor -3.1 \rfloor = -4 $

床関数、ガウス関数、整数部分は全部同じものです。

数直線上で自分のすぐ左にある整数を持ってくるイメージ。

$ x $ が有理数のとき

$ a $ を整数、$ b $ を正整数とします。整数 $ q $ と $ 0 \leq r < b $ を満たす整数 $ r $ を用いて $ a = bq + r $ と表せるとすると、 $$ \left\lfloor \frac{a}{b} \right\rfloor = \left\lfloor q + \frac{r}{b} \right\rfloor = q $$ が成り立ちます。

天井関数

$ x \in \mathbb{R} $ 以上の最小の整数を $ \lceil x \rceil $ で表し、$ \lceil \cdot \rceil $ を天井関数（ceiling function）と呼びます。

例：$ \lceil 1.2 \rceil = 2$、$ \lceil -3.1 \rceil = -3 $

$ x $ が有理数のとき

$ a $ を整数、$ b $ を正整数とします。整数 $ q $ と $ 0 \leq r < b $ を満たす整数 $ r $ を用いて $ a = bq - r $ と表せるとすると、 $$ \left\lceil \frac{a}{b} \right\rceil = \left\lceil q - \frac{r}{b} \right\rceil = q $$ が成り立ちます。

不等式評価

床関数

$x \in \mathbb{R}$ に対し、

$$ x - 1 < \lfloor x \rfloor \leq x $$

が成り立ちます。$ \lfloor x \rfloor \leq x < \lfloor x \rfloor + 1 $ の形で使うこともあります。

また、$a, b \in \mathbb{R}$ とすると

• $ a \leq b \Rightarrow \lfloor a \rfloor \leq \lfloor b \rfloor $
• $ \lfloor a \rfloor < \lfloor b \rfloor \Rightarrow a < b$

となります（逆は✗）。さらに、$a$ が整数のときは $$ a \leq b \Leftrightarrow a \leq \lfloor b \rfloor $$ が成り立ちます。

天井関数

$x \in \mathbb{R}$ に対し、

$$ x \leq \lceil x \rceil < x + 1 $$

が成り立ちます。$ \lceil x \rceil - 1 < x \leq \lceil x \rceil $ の形で使うこともあります。

また、$a, b \in \mathbb{R}$ とすると

• $ a \leq b \Rightarrow \lceil a \rceil \leq \lceil b \rceil $
• $ \lceil a \rceil < \lceil b \rceil \Rightarrow a < b$

となります（逆は✗）。さらに、$b$ が整数のときは $$ a \leq b \Leftrightarrow \lceil a \rceil \leq b $$ が成り立ちます。

noshi さんの記事 にも色々載っていてありがたいです。

noshi91.hatenablog.com

切り捨て除算を使った実装

C++ や Rust の整数除算は、小数点以下を切り捨てる仕様になっています *1 。すなわち、除算の結果が正のときは floor、負のときは ceil のような挙動をします。この項の目標は、割り算結果の floor や ceil を切り捨て除算で表現することです。

実数 $ x $ を $ 0 $ 方向に丸めたもの（小数点以下を捨てたもの）を $ \mathrm{round}(x) $ と書くことにします。

例：$ \mathrm{round}(5 / 3) = 1 $、$ \mathrm{round}(-5 / 3) = -1 $

$ b > 0 $ のとき、以下が成り立ちます：

$$ \left\lfloor \frac{a}{b} \right\rfloor = \begin{cases} \mathrm{round}(a / b) & (a \geq 0) \\ \mathrm{round}((a + 1) / b) - 1 & (a < 0) \end{cases} $$

証明（クリックで展開）

$ a \geq 0 $ のときは明らか。
$ a < 0 $ のとき $ \lfloor a / b \rfloor = \mathrm{round}((a + 1 ) / b) - 1 $ が成り立つことを示す。
整数 $ q $ と $ 0 \leq r < b $ を満たす整数 $ r $ を用いて $$ a + 1 = bq + r $$ と書けるとする。$ b \mid a+1 $ か否かで場合分けをする。
$ r = 0 $ のとき、 $$ \begin{split} (\text{左辺}) &= \left\lfloor \frac{bq - 1}{b} \right\rfloor \\\ &= \left\lfloor \frac{b(q-1) + (b - 1)}{b} \right\rfloor \\\ &= \left\lfloor q-1 + \frac{(b - 1)}{b} \right\rfloor \\\ &= q - 1 \end{split} $$ および $$ (\text{右辺}) = \mathrm{round}\left(\frac{bq}{b}\right) - 1 = q - 1 $$ となる。
$ r > 0 $ のとき、$ 0 \leq r - 1 < b$ と $ a = bq + (r - 1) $ を用いて $$ (\text{左辺}) = \left\lfloor q + \frac{r - 1}{b} \right\rfloor = q $$ また、 $$ (\text{右辺}) = \mathrm{round}\left(q + \frac{r}{b}\right) - 1 $$ $ a = bq + (r - 1) < 0 $ より $ q < 0 $ であり、$ q $ は整数なので $ q \leq -1 $。
$ 0 \leq r/b < 1 $ とあわせると $ q + r/b < 0 $ が分かるので、 $$ \mathrm{round}\left(q + \frac{r}{b}\right) = q + 1 $$ よって、 $$ (\text{右辺}) =(q+1) - 1 = q $$ となる。

$$ \left\lceil \frac{a}{b} \right\rceil = \begin{cases} \mathrm{round}((a - 1) / b) + 1 & (a > 0)\\ \mathrm{round}(a / b) & (a \leq 0) \end{cases} $$

証明（クリックで展開）

$ a \leq 0 $ のときは明らか。
$ a > 0 $ のとき $ \ceil a / b \rceil = \mathrm{round}((a - 1 ) / b) + 1 $ が成り立つことを示す。
整数 $ q $ と $ 0 \geq r < b $ を満たす整数 $ r $ を用いて $$ a - 1 = bq - r $$ と書けるとする。$ b \mid a-1 $ か否かで場合分けをする。
$ r = 0 $ のとき、 $$ \begin{split} (\text{左辺}) &= \left\lceil \frac{bq + 1}{b} \right\rceil \\\ &= \left\lceil \frac{b(q+1) - (b-1)}{b} \right\rceil \\\ &= \left\lceil q+1 - \frac{(b-1)}{b} \right\rceil \\\ &= q + 1 \end{split} $$ および $$ (\text{右辺}) = \mathrm{round}\left(\frac{bq}{b}\right) + 1 = q + 1 $$ となる。
$ r > 0 $ のとき、$ 0 \leq r - 1 < b $ と $ a = bq - (r - 1) $ を用いて $$ (\text{左辺}) = \left\lceil q - \frac{r - 1}{b} \right\rceil = q $$ また、 $$ (\text{右辺}) = \mathrm{round}\left(q - \frac{r}{b}\right) + 1 $$ $ a = bq - (r - 1) > 0 $ より $ q > 0 $ であり、$ q $ は整数なので $ q \geq 1 $。
$ 0 \leq r/b < 1 $ とあわせると $ q - r/b > 0 $ が分かるので、 $$ \mathrm{round}\left(q - \frac{r}{b}\right) = q - 1 $$ よって、 $$ (\text{右辺}) =(q-1) + 1 = q $$ となる。

$ b < 0 $ のときは、$ a \leftarrow -a,~b \leftarrow -b $ とすれば上の場合に帰着できます。競プロ用テンプレートに入れておくと便利。

template <class T>
T div_floor(T a, T b) {
    if (b < 0) a = -a, b = -b;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}

template <class T>
T div_ceil(T a, T b) {
    if (b < 0) a = -a, b = -b;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}

オーバーフローを避けて $ab$ と $c$ を比較する

この問題 で話題になったやつ。

$ a, b, c $ を正整数とします。$ ab $ と $ c $ の大小比較をしたいが、積 $ ab $ を求めようとするとオーバーフローして困る場面があります。

$ = $ と $ \leq $ さえ判定できれば他はこれらの組み合わせでできるので*2、$ = $ と $ \leq $ だけ考えます。

$ = $ については、

$$ ab = c \Leftrightarrow (a \mid c) \land \left(b = \frac{c}{a}\right) $$

です。$ \leq $ については、

$$ ab \leq c \Leftrightarrow b \leq \frac{c}{a} \Leftrightarrow b \leq \left\lfloor \frac{c}{a} \right\rfloor $$

より $ b \leq \lfloor c / a \rfloor $ が成り立つかどうかを見れば良いです。

このタイミングで言うのもなんですが、$ b/c $ と $ d/a $ の連分数展開を見比べれば $ ab $ と $ cd $ の大小比較ができるので、そっちを使っても良いと思います。

平方分割

$n$ を正整数とします。$x$ が正整数を動くとき、$\left\lfloor n / x\right\rfloor$ が取る値は

$$ 0, 1, 2, \ldots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \ldots, \lfloor n / 2 \rfloor, \lfloor n / 1 \rfloor $$

のいずれかです。列の前半は $ \left\lfloor n / x\right\rfloor $ が小さい場合、後半は $ x $ が小さい場合に対応しています。

種類数が $\lfloor n / \lfloor \sqrt{n} \rfloor \rfloor + \lfloor n \rfloor = O(\sqrt{n})$ しかないので DP の状態が減らせて嬉しい、みたいなことはよく起こります（例1 例2）。

数列 $a$ を

$$ a = (0, 1, 2, \ldots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \ldots, \lfloor n / 2 \rfloor, \lfloor n / 1 \rfloor) $$

とし、$ s = \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor $ とおきます。このとき、

$$ a_i = \begin{cases} i & (i \leq s) \\ \left\lfloor \frac{n}{s + \lfloor \sqrt{n} \rfloor - i} \right\rfloor & (i > s) \end{cases} $$

が成り立ちます。また、$ a $ における $ v $ のインデックスを $ a_v^{-1} $ と書くことにすると

$$ a_{v}^{-1} = \begin{cases} v & (v \leq s) \\ s + \lfloor \sqrt{n} \rfloor - \lfloor n / v \rfloor & (v > s) \end{cases} $$

となります。$ \lfloor n / i \rfloor = v $ かつ $ v > s $ のとき $ \lfloor n / v \rfloor = i $ が成り立つことを使っています。

証明（クリックで展開）

$ \lfloor n / i \rfloor = v $ かつ $ v > s $ とする。このとき、$ 0 \leq r < i $ を満たす整数 $ r $ が存在して $$ n = iv + r $$ が成り立っている。
$ r < v $ であることを示したい。そのためには、$ i \leq v $ となることが分かれば十分である。
$ i \geq n / \lfloor \sqrt{n} \rfloor $ と仮定すると、 $$ \frac{n}{i} \leq \frac{n}{n / \lfloor \sqrt{n} \rfloor} = \lfloor \sqrt{n} \rfloor $$ より、 $$ v = \left\lfloor \frac{n}{i} \right\rfloor \leq \lfloor \sqrt{n} \rfloor \leq \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor = s $$ となり矛盾。
よって、$ i < n / \lfloor \sqrt{n} \rfloor $ なので、$ i \leq s < v $ が成り立つ。

$ \left\lfloor \frac{n}{ab} \right\rfloor = \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor $

$ n, a, b $ を正整数とすると、

$$ \left\lfloor \frac{n}{ab} \right\rfloor = \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor $$

が成り立ちます。

証明（クリックで展開）

$ q $ を整数、$ r $ を $ 0 \leq r < ab $ を満たす整数とし、 $$ n = abq + r $$ と書けるとする。 このとき、 $$ \left\lfloor \frac{n}{ab} \right\rfloor = q $$ である。また、 $$ \begin{split} \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor &= \left\lfloor \left\lfloor bq + \frac{r}{a} \right\rfloor / b \right\rfloor \\\ &= \left\lfloor \left( bq + \left\lfloor \frac{r}{a} \right\rfloor \right) / b \right\rfloor \\\ &= \left\lfloor q + \left\lfloor \frac{r}{a} \right\rfloor / b \right\rfloor \\\ &= q + \left\lfloor \left\lfloor \frac{r}{a} \right\rfloor / b \right\rfloor \end{split} $$ ここで、$ \lfloor r/a \rfloor \geq b $ と仮定すると、$ r/a \geq b$ すなわち $ r \geq ab $ となり矛盾。
よって、$ \lfloor r/a \rfloor < b $ となるので $$ \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor = q + \left\lfloor \left\lfloor \frac{r}{a} \right\rfloor / b \right\rfloor = q $$ が成り立つ。

Sum of Floor of Linear

$ n, m, a, b $ が与えられます。

$$ \sum_{i = 0}^{n - 1} \left\lfloor \frac{ai + b}{m} \right\rfloor $$

を求めてね。

$ O(\log(\min \lbrace n, m, a \rbrace)) $ 時間で解けるらしいです。詳しくは えびちゃんの記事 などを参照してください。

rsk0315.hatenablog.com

*1:python の場合、// 演算子は床関数と同じ挙動をします。

*2:$ ab \geq c \Leftrightarrow \lnot (ab \leq c) \lor (ab = c) $ など