以下、\(A\) が最適な整数列であるとします。これは \(i\geq 2\) に対して、\(A_i\) が \(A_{i-1}\) より大きな最小の \(i\) の倍数であるものです。

[1] \(O(X^{1/2})\) 時間での解法

まずは時間計算量 \(O(X^{1/2})\) の解法について説明します（この解法は TLE となることが想定されています）。

整数列 \(B\) を、\(B_i = A_i / i\) により定めます。\(B_{i+1} = \lfloor\frac{iB_i}{i+1}\rfloor + 1 = B_{i} + 1 - \lceil\frac{B_i}{i+1}\rceil\) が成り立ちます。

次が成り立つことが容易に分かります：

• \(B_i\) は広義単調減少である
• \(B_i < i\) ならば、\(B_{i+1} = B_i\)

\(B_i\) の広義単調減少性より、\(B_n < n\) となる \(n\) が存在します。それ以降では \(B\) は定数列なので、その部分の総和をまとめて計算することができます。したがって、\(B_n < n\) が成り立つまで数列 \(B\) を計算すれば、本問題を解くことができます。

この解法の計算量、つまり \(B_n < n\) となる \(n\) の大きさを評価しましょう。大雑把に \(B_{i+1}\) と \(\frac{iB_i}{i+1}\) が十分近い、つまり \(iB_i\) がほぼ定数であると考えると、\(n\) が \(\sqrt{X}\) 程度のときに \(B_n < n\) が成り立ちそうです。より詳しく議論すると、例えば次が証明できます：

• 任意の \(i\) に対して、\(B_i < \frac{X}{i} + i\) が成り立つ。

特に、\(m = \lceil \sqrt{X} \rceil\) とすると、\(B_m < \frac{X}{m} + m \leq 2m\) が成り立ち、\(B_{2m} \leq B_m < 2m\) より\(n = 2m = 2\lceil \sqrt{X} \rceil\) に対して \(B_n < n\) が成り立つことが分かります。特に、この解法の時間計算量は \(O(X^{1/2})\) となります。

[2] \(O(X^{1/3})\) 時間での解法

[1] の計算の一部を上手くまとめましょう。

\(B_i - B_{i+1} = \lceil \frac{B_i}{i+1}\rceil - 1\) と\(B\) の広義単調減少性より、次が成り立つことが分かります：

• \(B_1 - B_2 \geq B_2 - B_3\geq \cdots\)

そこで、\(B_n - B_{n+1} = \cdots = B_{m-1} - B_m\) が成り立つような \(B_n, \ldots, B_{m-1}\) をまとめて扱うことにしましょう。

\(n\) が与えられたとき、\(B_n - B_{n+1} = B_i - B_{i+1}\) となる \(i\) の範囲を求めることは \(O(1)\) 時間で行えます。また、\(\sum_{i=n}^{m-1} iB_i\) の計算も、\(O(1)\) 時間で行えます（\(\sum_{k=0}^{n-1}k^2=\frac{1}{6}(n-1)n(2n-1)\) などの式を用いる・多項式補間を行うなどの方法があります ）。

結局、\(B_i - B_{i+1}\) のとる値の種類数を \(n\) としたとき、本問題は \(O(n)\) 時間で解くことができます。

\(B_i - B_{i+1}\) の種類数が \(O(X^{1/3})\) であることは、例えば次のように示されます：

• \(n = \lceil X^{1/3}\rceil\) とする。このとき [1] 内の評価より、\(B_n < X^{2/3} + n\) が成り立つ。
• したがって、\(B_n - B_{n+1} = \lceil \frac{B_n}{n+1}-1\rceil \leq \lceil \frac{X^{2/3}}{n+1}\rceil\leq n\) が成り立つ。
• \(B_1 - B_2, \ldots, B_{n-1} - B_{n}\) までの種類数は \(n-1\) 以下である。\(B_n - B_{n+1}\) 以降の種類数は \(n+1\) 以下である（\(0, 1, \ldots, n\) のどれかなので）。
• したがって、\(B_i - B_{i+1}\) の種類数は \(2n = 2 \lceil X^{1/3}\rceil\) 以下である。