差分
この文書の現在のバージョンと選択したバージョンの差分を表示します。
| 両方とも前のリビジョン 前のリビジョン | |||
|
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}$ となる。 | ||
