差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
programming_algorithm:contest_history:atcoder:2020:0627_abc172 [2020/06/28]
ikatakos
programming_algorithm:contest_history:atcoder:2020:0627_abc172 [2020/06/28] (現在)
ikatakos [$O(\sqrt{N})$ 解法]
ライン 74: ライン 74:
 「$N$ までに倍数が $b$ 個ある最大の $a$」は、$a = \dfrac{N}{b}$ で求められる。 「$N$ までに倍数が $b$ 個ある最大の $a$」は、$a = \dfrac{N}{b}$ で求められる。
  
-要は $a \times b \le N$ なので、ちょうど ​$\sqrt{N}$ で $a,b$ の大小が切り替わる。+要は $a \times b \le N$ なので、$\sqrt{N}$ ​付近で $a,b$ の大小が切り替わる。
  
 $a \lt b$ の範囲は $a$ を中心に計算し、$a \gt b$ の範囲は $b$ を中心に計算すると、探索範囲の上限は $\sqrt{N}$ となる。 $a \lt b$ の範囲は $a$ を中心に計算し、$a \gt b$ の範囲は $b$ を中心に計算すると、探索範囲の上限は $\sqrt{N}$ となる。
programming_algorithm/contest_history/atcoder/2020/0627_abc172.txt · 最終更新: 2020/06/28 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0