# yukcoder No.2221 Set X 解説

[問題へのリンク](https://yukicoder.me/problems/no/2221)

$\lfloor \frac{A_i}{X} \rfloor\ (1\leq i \leq N)$ の種類数の計算方法を考えます。

$A_{i+1}-A_i < X\ (1\leq i \leq N-1)$ のとき、$\lfloor \frac{A_{i+1}}{X} \rfloor - \lfloor \frac{A_i}{X} \rfloor$ は $0$ か $1$ であるため、$1 \leq i \leq N$ の範囲で $\lfloor \frac{A_i}{X} \rfloor$ は $\lfloor \frac{A_1}{X} \rfloor$ 以上 $\lfloor \frac{A_N}{X} \rfloor$ 以下の値をすべて取ります。よって $\lfloor \frac{A_i}{X} \rfloor\ (1\leq i \leq N)$ の種類数は $\lfloor \frac{A_N}{X} \rfloor - \lfloor \frac{A_1}{X} \rfloor + 1$ 種類です。

$X \leq A_{i+1}-A_i$ のとき、$\lfloor \frac{A_i}{X} \rfloor < \lfloor \frac{A_{i+1}}{X} \rfloor$ が成り立つので、そのような $i$ で列を分離させると上記の場合に帰着できます。

以上をまとめると、 $X \leq A_{i+1}-A_i$ が成り立つ $i$ を $i_1 < i_2 < \dots < i_k$ として、$\lfloor \frac{A_i}{X} \rfloor\ (1\leq i \leq N)$ の種類数は

$(\lfloor \frac{A_{N}}{X} \rfloor - \lfloor \frac{A_{i_k+1}}{X} \rfloor+1)+ (\lfloor \frac{A_{i_k}}{X} \rfloor - \lfloor \frac{A_{i_{k-1}+1}}{X} \rfloor + 1) + \dots + (\lfloor \frac{A_{i_2}}{X} \rfloor - \lfloor \frac{A_{i_1+1}}{X} \rfloor + 1) + (\lfloor \frac{A_{i_1}}{X} \rfloor - \lfloor \frac{A_{1}}{X} \rfloor + 1)$

という風に計算できます。

$X$ の昇順に見ていけば $i$ の管理は全体で $O(N\log N)$ で行えます。$f(X)$ について愚直に計算すると $O(k)$ だけかかりますが、$(X+1) \times (k+1) \leq f(X)$ が成り立ち、$f(X) < f(1)=2N$ であるような $X$ だけ興味があるので、$k+1 \leq \lfloor \frac{2N}{X+1} \rfloor$ が成り立つような $X\ (1\leq X\leq 2N)$ に対してだけ計算すればいいです。これは $O(N\log N)$ で行えます。

[実装例（PyPy3）](https://yukicoder.me/submissions/841165)