{"problem":{"name":"[AHOI2024 初中组 / 科大国创杯初中组 2024] 立方根","description":{"content":"小可可想计算所有不大于 $x$ 的正整数的立方根下取整之和，但是她不会做，你能帮帮她吗？ 为了彻底帮小可可弄懂这个问题，你需要回答 $q$ 组询问，对于每组询问给定的一个正整数 $x_i$，输出： $$\\sum _{j=1} ^{x_i} \\lfloor j^{\\frac{1}{3}} \\rfloor$$ 其中，$\\lfloor x \\rfloor$ 表示不大于 $x$ 的最大整数。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10373"},"statements":[{"statement_type":"Markdown","content":"小可可想计算所有不大于 $x$ 的正整数的立方根下取整之和，但是她不会做，你能帮帮她吗？\n\n为了彻底帮小可可弄懂这个问题，你需要回答 $q$ 组询问，对于每组询问给定的一个正整数 $x_i$，输出：\n\n$$\\sum _{j=1} ^{x_i} \\lfloor j^{\\frac{1}{3}} \\rfloor$$\n\n其中，$\\lfloor x \\rfloor$ 表示不大于 $x$ 的最大整数。\n\n## Input\n\n第一行一个正整数 $q$。\n\n接下来 $q$ 行，第 $i$ 行一个正整数 $x_i$。\n\n**保证给出的 $\\bm{x_1 \\sim x_q}$ 单调不降。**\n\n## Output\n\n$q$ 行，每行一个正整数，表示该组询问的答案。\n\n**请注意答案的范围。**\n\n[samples]\n\n## Background\n\n**本题的数据不是官方数据。**\n\n**本题征集（能够上传到这里的）官方数据。**\n\n**（没法上传到这里的）官方数据：<https://www.luogu.com.cn/training/499869>**\n\n**本题民间数据下载：<http://8.136.99.126/blog/3/67f0c2307aadac7b413b837b>**\n\n**特别提示：**\n\n1. 请使用 `(int) cbrt(x + 0.5)` 计算 $\\lfloor \\sqrt[3]{x} \\rfloor$ 的值，否则可能会出现精度误差。\n2. 本题包含两组针对时间复杂度为 $O(q\\sqrt[3]{x})$ 的算法的 hack 数据（#11 和 #12）。\n\n## Note\n\n### 样例 1 解释\n\n$1 \\sim 10$ 的立方根下取整的结果是：$1,1,1,1,1,1,1,2,2,2$。\n\n### 数据范围\n\n对于 $20\\%$ 的数据，$x_q,q \\le 1000$。\n\n对于另外 $20\\%$ 的数据，$q=1$。\n\n对于另外 $20\\%$ 的数据，$q \\le 5000$。\n\n对于另外 $20\\%$ 的数据，$q \\le 10^5$，$x_q \\le 10^6$。 \n\n对于 $100\\%$ 的数据，$1 \\le q \\le 2 \\times 10^5$，$1 \\le x_1 \\le x_2 \\le \\ldots \\le x_q \\le 10^{12}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10373","tags":["数学","递推","2024","安徽","O2优化","前缀和","分块","双指针 two-pointer","科创活动","初中活动","科大国创杯"],"sample_group":[["2\n5\n10","5\n13"]],"created_at":"2026-03-03 11:09:25"}}