Below, we assume that \(A\) is an optimal sequence, where \(A_i\) is the smallest multiple of \(i\) greater than \(A_{i-1}\) for \(i\geq 2\).

[1] A solution in \(O(X^{1/2})\) time

We first explain an \(O(X^{1/2})\) solution (which is expected to get TLE).

Let a sequence \(B\) defined by \(B_i = A_i / i\). We have \(B_{i+1} = \lfloor\frac{iB_i}{i+1}\rfloor + 1 = B_{i} + 1 - \lceil\frac{B_i}{i+1}\rceil\).

It is easy to see the following:

• \(B_i\) is non-increasing
• \(B_{i+1} = B_i\) if \(B_i < i\)

Since \(B_i\) is non-increasing, there is \(n\) such that \(B_n < n\). Afterward, it is a constant sequence, where the sum can be computed altogether. Thus, the problem can be solved by computing the sequence \(B\) until \(B_n < n\) holds.

Let us evaluate the complexity of this solution, that is, the size of \(n\) such that \(B_n < n\). If we roughly consider that \(B_{i+1}\) and \(\frac{iB_i}{i+1}\) are close enough, that is, \(iB_i\) is almost a constant, it seems probable that \(B_n < n\). A more detailed argument can, for example, prove the following:

• \(B_i < \frac{X}{i} + i\) for every \(i\).

Specifically, if we let \(m = \lceil \sqrt{X} \rceil\), we have \(B_m < \frac{X}{m} + m \leq 2m\), and it follows from \(B_{2m} \leq B_m < 2m\) that \(B_n < n\) for \(n = 2m = 2\lceil \sqrt{X} \rceil\). Especially, the time complexity of the solution above is \(O(X^{1/2})\).

[2] A solution in \(O(X^{1/3})\) time

Let us try to put together some computations in [1].

Since \(B_i - B_{i+1} = \lceil \frac{B_i}{i+1}\rceil - 1\) and \(B\) is non-increasing, it can be seen that the following holds:

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

Let us deal with \(B_n, \ldots, B_{m-1}\) where \(B_n - B_{n+1} = \cdots = B_{m-1} - B_m\) holds altogether.

For a given \(n\), the range of \(i\) where \(B_n - B_{n+1} = B_i - B_{i+1}\) holds can be found in \(O(1)\) time. Additionally, \(\sum_{i=n}^{m-1} iB_i\) can be found in \(O(1)\) time, too (by using formulae such as \(\sum_{k=0}^{n-1}k^2=\frac{1}{6}(n-1)n(2n-1)\), or polynomial interpolation, etc).

In the end, if \(B_i - B_{i+1}\) takes \(n\) different values, the problem can be solved in \(O(n)\) time.

Below is a proof that \(B_i - B_{i+1}\) takes \(O(X^{1/3})\) different values.

• Let \(n = \lceil X^{1/3}\rceil\). Then, from the evaluations in [1], we have \(B_n < X^{2/3} + n\).
• Thus, we have \(B_n - B_{n+1} = \lceil \frac{B_n}{n+1}-1\rceil \leq \lceil \frac{X^{2/3}}{n+1}\rceil\leq n\).
• There are at most \(n-1\) different values among \(B_1 - B_2, \ldots, B_{n-1} - B_{n}\), and at most \(n+1\) different values after \(B_n - B_{n+1}\) (because they are among \(0, 1, \ldots, n\)).
• Therefore, \(B_i - B_{i+1}\) takes at most \(2n = 2 \lceil X^{1/3}\rceil\) different values.