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

The answer changes when \(\lfloor\sqrt{X}\rfloor\) changes.

Let \(f_n\) be the answer when \(X=n\), then \(f_n=f_{n-1}+[\sqrt{n} \in \mathbb{N}^+]f_{\sqrt{n}}\).

Let \(g_n=\sum\limits_{i=1}^{n}f_i\), then we can find that \(g_n=g_{n-1}+g_{\lfloor\sqrt{n}\rfloor}(n \ge 2)\), and \(f_n=g_n-g_{n-1}=g_{\lfloor\sqrt{n}\rfloor}\).

Optimization

Let \(s_n=g_{kn}\), when \(k\) is a constant.

We can get \(s_1,s_2,\cdots,s_{\lfloor{X_{max} \over k}\rfloor}\) and put them in the code.

Then, we can also spend \(O(X^{1 \over 4})\) times precalculating \(g_1,g_2,\cdots,g_{X^{1 \over 4}}\).

So it can be solved by:

1. If \(X \le X_{max}^{1 \over 4}\), return the precalculated \(g_X\);
2. If \(k|X\) return \(s_{X \over k}\);
3. Get the value of \(g_{x-1}+g_{\lfloor\sqrt{X}\rfloor}\).

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