No matter how, the terms of \(A\) becomes \(1\) at the very early stage, so we can ignore the number of operations.

\(O(X^{1/2})\) Solution

Let \(dp[x]\) (dp stands for Dynamic Programming) be the number of kinds of \(A\) that can be obtained from the initial value \(A_1=x\). By considering the value for \(A_2\), we have \(dp[x]=\sum_{i=1}^{\lfloor \sqrt{x}\rfloor}dp[i]\). By this equation, \(dp[x]\) can be computed in the increasing order of \(x\). By filling \(dp\) table in the range of \(i\leq \lfloor \sqrt{X}\rfloor\) while computing the cumulative sum, \(dp[X]\) can be solved in an \(O(\sqrt{X})\) time.

\(O(X^{1/4})\) Solution

We define \(dp[x]\) just as before. In the \(O(X^{1/2})\) solution, we only considered the value for \(A_2\); this time, we consider the value for \(A_3\). When \(A_1=x\) and \(A_3=i\), \(A_2\) can be any integer between \(i^2\) and \(\sqrt{x}\) (inclusive). Therefore, we have \(dp[x]=\sum_{i=1}^{\lfloor x^{1/4}\rfloor}(\lfloor\sqrt{x}\rfloor-i^2+1)dp[i]\). By computing for \(i\leq \lfloor X^{1/4} \rfloor\) in the same way as \(O(X^{1/2})\) solution, \(dp[X]\) can be solved in a total of \(O(X^{1/4})\) time.

Therefore, the problem can be solved in an \(O(X^{1/4})\) time for each query.

Sample code (C)

Note that it can be solved in an \(O(1)\) time for each query by using cumulative sums appropriately and spending \(O(X^{1/4})\) time for precalculation.

Sample code (C)