差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | |||
| programming_algorithm:contest_history:atcoder:2020:0627_abc172 [2020/06/28] – ikatakos | programming_algorithm:contest_history:atcoder:2020:0627_abc172 [2020/06/28] (現在) – [$O(\sqrt{N})$ 解法] ikatakos | ||
|---|---|---|---|
| 行 74: | 行 74: | ||
| 「$N$ までに倍数が $b$ 個ある最大の $a$」は、$a = \dfrac{N}{b}$ で求められる。 | 「$N$ までに倍数が $b$ 個ある最大の $a$」は、$a = \dfrac{N}{b}$ で求められる。 | ||
| - | 要は $a \times b \le N$ なので、ちょうど | + | 要は $a \times b \le N$ なので、$\sqrt{N}$ |
| $a \lt b$ の範囲は $a$ を中心に計算し、$a \gt b$ の範囲は $b$ を中心に計算すると、探索範囲の上限は $\sqrt{N}$ となる。 | $a \lt b$ の範囲は $a$ を中心に計算し、$a \gt b$ の範囲は $b$ を中心に計算すると、探索範囲の上限は $\sqrt{N}$ となる。 | ||
