G - Sqrt Editorial by RatzielQ
\(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:
- If \(X \le X_{max}^{1 \over 4}\), return the precalculated \(g_X\);
- If \(k|X\) return \(s_{X \over k}\);
- 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.
posted:
last update: