分数次幂递推¶
预估时间限制：1.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
一个求值服务接到许多整数查询。每个答案又依赖两个较小参数的答案，请计算这些查询的精确值。
(本故事由GPT-6重写)
形式化问题描述¶
函数 \(F\) 的定义域和值域都是非负整数，并满足
\[
F(x)=3F\left(\max\{\lfloor x^{4/5}\rfloor-1,0\}\right)+2F\left(\left\lfloor\frac{x}{2}\right\rfloor\right)+x
\]
分数次幂表示实数意义下的幂，\(\lfloor\cdot\rfloor\) 表示向下取整。等式也适用于零，从而 \(F(0)=0\) .给出 \(N\) 个参数 \(a_i\) ，求每个 \(F(a_i)\) 的精确整数值，不取模。
输入格式¶
第一行整数 \(N\) ，表示查询数。第二行 \(N\) 个整数 \(a_1,\ldots,a_N\) .
输出格式¶
输出一行 \(N\) 个整数，以空格分隔，依次表示各个查询的答案。
样例¶
样例 1¶
输入¶
5
0 1 1000000000 5000 2
输出¶
0 1 12422138161640 8422275 4
样例 2¶
输入¶
6
0 0 1 2 3 4
输出¶
0 0 1 4 8 24
样例解释¶
第二组中，\(F(1)=1\) ，\(F(2)=4\) ，\(F(3)=8\) ；因为 \(\lfloor4^{4/5}\rfloor-1=2\) ，所以 \(F(4)=3F(2)+2F(2)+4=24\) .重复查询零时都输出零。
数据范围与保证¶
对所有数据，\(1\le N\le10^5\) ，\(0\le a_i\le10^9\) .查询可以重复。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |