ABC 204 E に関連します。
定義
| 表記 | 意味 | 例 |
|---|---|---|
| $\floor{x}$ | $x$ 以下の最大の整数 | $\floor{3.1} = 3$, $\floor{2.7} = 2$, $\floor{-2.2} = -3$, $\floor{2} = 2$ |
| $\ceil{x}$ | $x$ 以上の最小の整数 | $\ceil{3.1} = 4$, $\ceil{2.7} = 3$, $\ceil{-2.2} = -2$, $\ceil{2} = 2$ |
| $\rounded{x}$ | $x$ に最も近い整数 | $\rounded{3.1} = 3$, $\rounded{2.7} = 3$, $\rounded{-2.2} = -2$, $\rounded{2} = 2$ |
ただし、ここでは、整数 $n$ に対して $\rounded{n + 0.5}$ は未定義とします。すなわち、以下のスタンスということです。
- この記事中で $\rounded{x}$ を考えるときは $x - \floor{x} \neq 0.5$ を示す必要がある。
- $\rounded{n + 0.5} = n$ あるいは $\rounded{n + 0.5} = n + 1$ のように拡張した関数でも、この記事で示した性質は成り立つ。
定理と補題たち
Lemma 1: $\ForallL{n\in\N}{\sqrt{n}-\floor{\sqrt{n}} \neq 1/2}$
Proof
背理法による。 ある非負整数 $n$ に対し、整数 $m$ が存在して $\sqrt{n} = m+1/2$ が成り立つと仮定する。 $$n = (m+1/2)^2 = m^2+m+1/4$$ より、$n\in\Z$ かつ $n\notin\Z$ が成り立つので矛盾。$\qed$
Lemma 2: $$ \ForallL{x\in\R}{x\ge 0\implies -\tfrac12+\sqrt{\tfrac14+x}\le \sqrt{x} \lt \left(-\tfrac12+\sqrt{\tfrac14+x}\right)+\tfrac12} $$
Proof
右側は $\sqrt{x} \lt \sqrt{x+\tfrac14}$ より明らか。以下、左側を示す。 $$ \begin{aligned} -\tfrac12 + \sqrt{\tfrac14 + x} &\le -\tfrac12 + \sqrt{\left(\tfrac12+\sqrt{x}\right)^2} \\ &= -\tfrac12 + \left|\tfrac12 + \sqrt{x}\right| \\ &= \sqrt{x}. \qquad\qed \end{aligned} $$
Theorem 3: $$ \ForallL{n\in\N}{\Ceil{-\tfrac12+\sqrt{\tfrac14+n}} = \rounded{\sqrt{n}}} $$
Proof
任意に固定した $n\in\N$ に対し、$m = \Ceil{-\tfrac12+\sqrt{\tfrac14+n}}$ とする。 このとき、$m-\tfrac12 \lt \sqrt{n} \lt m+\tfrac12$ を示せばよい。
右側は Lemma 2 から従うので、以下では左側を示す。 $n = 0$ のとき明らかに成り立つので、以下 $n \gt 0$ とする。このとき $m \ge 1$ であることに注意する。 $m$ の定義から $m-1 \lt -\tfrac12 + \sqrt{\tfrac14+n}$ なので、 $$ \begin{aligned} m-1 &\lt -\tfrac12 + \sqrt{\tfrac14+n} \\ m - \tfrac12 & \lt \sqrt{\tfrac14+n} \\ n & \gt (m-\tfrac12)^2-\tfrac14 \\ &= m^2-m \end{aligned} $$ となる。整数性より $n\ge m^2-m+1$ なので、 $$ \begin{aligned} n &\ge m^2-m+1 \\ &\gt (m-\tfrac12)^2 \\ m-\tfrac12 &\lt \sqrt{n}.\qquad\qed \end{aligned} $$
Lemma 4: $\ForallL{n\in\N}{n\le \floor{\sqrt{n}}\floor{\sqrt{n}+1} \iff \sqrt{n} \lt \floor{\sqrt{n}}+\tfrac12}$
Proof
$m = \floor{\sqrt{n}}$ とおく。
($\implies$) 対偶を示す。$\sqrt{n}\ge m+\tfrac12 \implies n \gt m(m+1)$ を示す。 $$ \begin{aligned} n &\ge (m+\tfrac12)^2 \\ &= m^2+m+\tfrac14 \\ &\gt m(m+1). \end{aligned} $$
($\impliedby$) $\sqrt{n}\lt m+\tfrac12 \implies n \le m(m+1)$ を示す。 $$ \begin{aligned} n &\lt (m+\tfrac12)^2 \\ &= m^2 + m + \tfrac14 \end{aligned} $$ 整数性より、$n \le m^2+m$ が従う。$\qed$
Lemma 5: $$\ForallL{n\in\N}{n\gt 0, n\le\floor{\sqrt{n}}\floor{\sqrt{n}+1} \implies \frac{n}{\floor{\sqrt{n}}} \le \frac{n}{\floor{\sqrt{n}+1}} + 1}$$
Proof
$m = \floor{\sqrt{n}}$ とおく。対偶を考える。 $n/m \gt n/(m+1)+1 \implies n\gt m(m+1)$ を示す。 $$ \begin{aligned} n(m+1) &\gt nm + m(m+1) \\ n &\gt m(m+1). \qquad\qed \end{aligned} $$
Lemma 6: $$\ForallL{n\in\N}{n\gt 0, n\le\floor{\sqrt{n}}\floor{\sqrt{n}+1} \implies \Floor{\frac{n}{\floor{\sqrt{n}+1}}} \lt \Floor{\frac{n}{\floor{\sqrt{n}}}}}$$
Proof
$m = \floor{\sqrt{n}}$ とおく。$n = m(m+1)$ のときは明らかなので、$n \lt m(m+1)$ とする。 $n\lt m(m+1) \implies \floor{\tfrac{n}{m+1}} \lt \floor{\tfrac nm}$ を示す。
$m = \floor{\sqrt{n}}$ より、$m^2 = \floor{\sqrt{n}}^2 \le n$ であり、 $$ \Floor{\frac{n}{m+1}} \lt \frac{n}{m+1} \lt m \le \frac nm $$ となる。整数性より $m\le \floor{\tfrac nm}$ であり、$\floor{\tfrac{n}{m+1}}\lt \floor{\tfrac nm}$ が従う。$\qed$
Theorem 7: $$\ForallL{n\in\N}{n\gt 0, \Floor{\frac{n}{\floor{\sqrt{n}+1}}} + \floor{\sqrt{n}+1} = \Floor{\frac{n}{\rounded{\sqrt{n}}}} + \rounded{\sqrt{n}}}$$
Proof
$\floor{\sqrt{n}}+\tfrac12 < \sqrt{n}$ のとき $\floor{\sqrt{n}+1} = \rounded{\sqrt{n}}$ であり、明らかに成り立つ。 以下、$\sqrt{n} \lt \floor{\sqrt{n}}+\tfrac12$ とする。 このとき、$\rounded{\sqrt{n}} = \floor{\sqrt{n}}$ なので、以下を示せばよい。 $$ \sqrt{n} \lt \floor{\sqrt{n}}+\frac12 \implies \Floor{\frac{n}{\floor{\sqrt{n}+1}}} + 1 = \Floor{\frac{n}{\floor{\sqrt{n}}}}. $$ $m = \floor{\sqrt{n}}$ とおく。Lemma 4 より、$$n\le m(m+1) \implies \Floor{\frac{n}{m+1}}+1 = \Floor{\frac{n}{m}}$$ を示せばよい。 Lemma 5 から $$ \Floor{\frac nm}\le \frac nm\le \frac{n}{m+1}+1. $$ Lemma 6 および整数性から $$ \Floor{\frac{n}{m+1}}\le \frac{n}{m+1}\lt \Floor{\frac nm} $$ なので、 $$ \Floor{\frac nm}\le \frac{n}{m+1} + 1 \lt \Floor{\frac nm} + 1 $$ が成り立つ。 すなわち、$\floor{\frac nm} = \floor{\frac{n}{m+1}}+1$ となる。$\qed$
Claim 8: $$\ForallL{n\in\N}{n\gt 0 \implies \floor{\sqrt{n}}\le \Floor{\frac{n}{\floor{\sqrt{n}}}} \le \floor{\sqrt{n}+2}}$$
Proof
$m = \floor{\sqrt{n}}$ とおく。$m \le \sqrt{n} \lt m+1$ と整数性より $m^2\le n\le m^2+2m$ が成り立つ。よって $m\le \floor{n/m}\le n/m\le m+2$ が従う。
系
Corollary 9: Theorem 7 より、ABC 204 E 公式解説 の中で $t = \rounded{\sqrt{D}}-1$ を使っている部分で、代わりに $t = \floor{\sqrt{D}}$ を使うことができます。
Corollary 10: 二分探索を用いることで、整数の範囲で（浮動小数点数の演算を経由せず）$\floor{\sqrt{n}}$ を求められることは有名ですが、Lemma 4 を利用することで $\rounded{\sqrt{n}}$ も整数の範囲で求めることができます。
fn rounded_sqrt(n: u64) -> u64 { let floor_sqrt = floor_sqrt(n); // よしなに match floor_sqrt.overflowing_mul(floor_sqrt + 1) { // n > floor_sqrt * (floor_sqrt + 1) なら floor_sqrt + 1 と等しい (mul, false) if n > mul => floor_sqrt + 1, // そうでない場合（積がオーバーフローした場合も含む）は floor_sqrt と等しい _ => floor_sqrt, } }
その他
一応確認として $1\le n\le 10^9$ の範囲で諸々の命題が成り立つことを確認していたのですが、整数の平方根の計算（指数探索による）を含む場合は 30 秒程度、浮動小数点数の計算のみの場合は 3 秒程度で済んだのでびっくりしました。
競プロをしているときの雑な感覚だと、$10^9$ 回程度の演算はそれなりの時間がかかりそうな気がしちゃうので（30 秒はそれなりの時間であるという見方もあるかも）。
p⇔q を示そうとして p⇒q と ¬q⇒¬p を示していました、どうして
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) August 19, 2023
証明を別のところで下書きしてから記事を書き始めたのですが、下書きの Lemma 4 の証明がこわれていて焦りました。
おわり
おわりです。久々に高校数学をやった気がしました。半年前は商の微分とかをやっていました。
