P10373 [AHOI2024 Junior / USTC Guochuang Cup Junior 2024] Cube Root

**The testdata for this problem is not official.** **We are collecting official testdata (that can be uploaded here).** **Official testdata (cannot be uploaded here): ** **Unofficial testdata download: ** **Special notes:** 1. Please use `(int) cbrt(x + 0.5)` to compute $\lfloor \sqrt[3]{x} \rfloor$, otherwise precision errors may occur. 2. This problem includes two hack test cases against algorithms with time complexity $O(q\sqrt[3]{x})$ (#11 and #12).

Xiaokeke wants to compute the sum of the floored cube roots of all positive integers not greater than $x$, but she does not know how. Can you help her? To fully help Xiaokeke understand this problem, you need to answer $q$ queries. For each query, given a positive integer $x_i$, output: $$\sum _{j=1} ^{x_i} \lfloor j^{\frac{1}{3}} \rfloor$$ Here, $\lfloor x \rfloor$ denotes the greatest integer not greater than $x$.

The first line contains a positive integer $q$. Then follow $q$ lines. The $i$-th line contains a positive integer $x_i$. **It is guaranteed that $\bm{x_1 \sim x_q}$ is non-decreasing.**

Output $q$ lines. Each line contains a positive integer, representing the answer to that query. **Please pay attention to the range of the answer.**

### Sample 1 Explanation The floored cube roots of $1 \sim 10$ are: $1,1,1,1,1,1,1,2,2,2$. ### Constraints For $20\%$ of the data, $x_q,q \le 1000$. For another $20\%$ of the data, $q=1$. For another $20\%$ of the data, $q \le 5000$. For another $20\%$ of the data, $q \le 10^5$, $x_q \le 10^6$. For $100\%$ of the data, $1 \le q \le 2 \times 10^5$, $1 \le x_1 \le x_2 \le \ldots \le x_q \le 10^{12}$. Translated by ChatGPT 5