[AHOI2024 初中组] 立方根
题目背景
**特别提示:**
1. 请使用 `(int) cbrt(x + 0.5)` 计算 $\lfloor \sqrt[3]{x} \rfloor$ 的值,否则可能会出现精度误差。
2. 本题包含两组针对时间复杂度为 $O(q\sqrt[3]{x})$ 的算法的 hack 数据(#11 和 #12)。
题目描述
小可可想计算所有不大于 $x$ 的正整数的立方根下取整之和,但是她不会做,你能帮帮她吗?
为了彻底帮小可可弄懂这个问题,你需要回答 $q$ 组询问,对于每组询问给定的一个正整数 $x_i$,输出:
$$\sum _{j=1} ^{x_i} \lfloor j^{\frac{1}{3}} \rfloor$$
其中,$\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。
输入输出格式
输入格式
第一行一个正整数 $q$。
接下来 $q$ 行,第 $i$ 行一个正整数 $x_i$。
**保证给出的 $\bm{x_1 \sim x_q}$ 单调不降。**
输出格式
$q$ 行,每行一个正整数,表示该组询问的答案。
**请注意答案的范围。**
输入输出样例
输入样例 #1
2
5
10
输出样例 #1
5
13
说明
### 样例 1 解释
$1 \sim 10$ 的立方根下取整的结果是:$1,1,1,1,1,1,1,2,2,2$。
### 数据范围
对于 $20\%$ 的数据,$x_q,q \le 1000$。
对于另外 $20\%$ 的数据,$q=1$。
对于另外 $20\%$ 的数据,$q \le 5000$。
对于另外 $20\%$ 的数据,$q \le 10^5$,$x_q \le 10^6$。
对于 $100\%$ 的数据,$1 \le q \le 2 \times 10^5$,$1 \le x_1 \le x_2 \le \ldots \le x_q \le 10^{12}$。