えびちゃんの日記

えびちゃん（競プロ）の日記です。

平方根と整数除算まわりの性質メモ

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 秒はそれなりの時間であるという見方もあるかも）。

証明を別のところで下書きしてから記事を書き始めたのですが、下書きの Lemma 4 の証明がこわれていて焦りました。

おわり

おわりです。久々に高校数学をやった気がしました。半年前は商の微分とかをやっていました。

rsk0315.hatenablog.com