問題概要
問題文 → ■
$N$ を正の整数とし，$S = \bigl\lbrace\lfloor N/x\rfloor\mid x\in\lbrace 1,2,\ldots,N\rbrace\bigr\rbrace$ とします．$S$ の要素を昇順に列挙しましょう．
以下，$x$ や $n$ と書けば正整数を表すものとします．
解法
$S$ がどういう集合かを理解しましょう．
関数 $x\mapsto \frac{N}{x}-\frac{N}{x+1}$ は単調減少なので，$n$ を次が成り立つようにとれます．
- $1\leq x < n$ ならば $\frac{N}{x}-\frac{N}{x+1}\geq 1$
- $n\leq x \leq N$ ならば $\frac{N}{x}-\frac{N}{x+1}< 1$
すると，$\lfloor\frac{N}{x}\rfloor$ を $x=1,2,3,\ldots$ の順に求めていくと，その値は次のようになります．
- $x=1,2,\ldots,n$ の範囲で $\lfloor\frac{N}{x}\rfloor$ は狭義単調に減少する．
- $x=n,n+1,\ldots,N$ の範囲では $\lfloor\frac{N}{x}\rfloor$ は $0$ または $1$ ずつ減少する．したがってこの範囲の $x$ に対して $\lfloor\frac{N}{x}\rfloor$ は $1$ 以上 $\lfloor\frac{N}{n}\rfloor$ 以下の値をちょうど 1 回ずつとる．
したがって，$S$ の要素を昇順に列挙したものは次のようになります：
$$1, 2, 3, \ldots, \biggl\lfloor\dfrac{N}{n}\biggr\rfloor,\biggl\lfloor\dfrac{N}{n-1}\biggr\rfloor,\ldots,\biggl\lfloor\frac{N}{1}\biggr\rfloor$$
prefix 部分は単純な連番であり，suffix 部分は floor 内の分母が連番です．
境界 $n$ を計算するには二分探索してもよいですし，2 次方程式を解くことを考えてもよいです．また，商を列挙しながら線形に探索しても計算量オーダーの悪化はありません（定数倍には少し影響するかも）．
- 解答例（27ms）
ここから実装をわずかにいじるだけで，少し高速化します．びっくり高速化．
→（2024/04/05）Library Checker 最新のジャッジ環境では実行時間の改善は見られなくなりました（整数の除算が高速になった）ジャッジ環境によっては改善になるかもしれません。
- 解答例（28ms）
変更前：N / i
変更後：double(N) / i
これ個人的には驚きが多かったのですが，Nyaan さんのライブラリを勉強すると次のような記述が見つかります．
64bit整数同士の除算は最悪ケースで80クロックと低速なのに対してdouble型同士は11クロックとはるかに高速であり、また $N=10^{12}$ 程度の大きさ同士の切り捨て除算ならばdouble型で計算しても誤差が発生しないことが規格で保証されている
https://nyaannyaan.github.io/library/multiplicative-function/prime-counting-faster.hpp.htm
現在，多くのプログラミング言語の浮動小数点数は，IEEE 754 の規格を満たすように実装されているようです．したがって，$a,b$ が整数で double 型で誤差なしで表せる（$2$ 進法有効数字 53 桁以下）ならば，double(a)/double(b) の計算結果は実数としての正確な計算結果 a/b を丸めたものです．
$a/b$ が整数になるならば，計算結果は正しくなります．
そうでないならば，$a/b$ とその最も近い整数の差は $1/b$ 以上です．これは $a/b$ の $\frac{1}{a}$ 倍で，$a$ が $2^{53}$ より十分小さければ丸めによって $\frac{1}{a}$ 倍以上に値が変わってしまうことはないため，floor や ceil の計算は正しく行えるということだと思います．
「十分小さければ」の部分について，私はこうした誤差の議論の細部に自信がないので，はっきりとこの制約までであれば正しい計算結果になると示すことはここではしません．
コメント
- $S$ の要素数を求める問題：■
- 商列挙のパフォーマンスはたまに話題になる印象があります．■とかも TL 勝負になっている人が居たような．あとは，想定解が倍数方向に調べる調和級数計算量で，見えた解法が商列挙なので TL 勝負発生ということもよくある話です．そういう意味ではパフォーマンスの良い実装を持っておく価値はまあまああるかもしれません．
- $S$ の要素を昇順に並べると，prefix と suffix それぞれで非常に簡潔な構造を持っています．したがって，$k$ 番目の商を取得したり，商が与えられたときにそれが $S$ の何番目の要素であるかを取得するといった計算が簡単にできます．このことから，floor(N/x) と書ける値を状態として dp を行う場合，Map（HashMap）などを使わずに配列の添字で dp テーブルを管理することができます（HashMap よりも数倍高速になったりする）．数論的関数周りの実装で基本的なテクニックだと思います．
