分数次幂递推: 题解¶
思路与贡献¶
标准程序保留出题人的递归求值及“小参数记忆化、大参数直接展开”策略。Codex（GPT-6）补充精确整数根核验与回退、显式零值边界，用未计算哨兵代替独立访问数组，并按输入中的最大参数减少小数据的分配。见 std.cpp。这些是同一算法的数值可靠性和存储修整。
设 \(U\) 为所有查询的最大值，令 \(C=\min(10^7,U+1)\) .分配长度为 \(C\) 的 64 位数组，未计算位置为 \(-1\) ，并令 \(Memo_0=0\) .求值时，若参数小于 \(C\) 且已缓存就直接返回，否则按递推式计算；结果只有在参数小于 \(C\) 时保存。超过阈值的重复查询会重复展开，不能把每个参数都只计算一次作为复杂度前提。
精确计算分数次幂的下取整¶
令 \(r=\lfloor x^{4/5}\rfloor\) ，等价条件为
浮点 pow 只用于产生候选值；必须用整数比较验证上式，成立才采用，否则二分查找真正的 \(r\) .所以正确性不依赖候选的舍入方向，也不假设误差最多为一。
在输入范围内 \(x^4\le10^{36}\) ，且 \(r<16000000\) .代码把宽整数表示为四个从高到低排列的 32 位块，用 64 位乘法和进位反复乘以底数，得到四次幂或五次幂。这些数都小于 \(2^{128}\) ；单块乘积加进位也在 64 位范围内。数组按字典序比较恰好等于无符号大整数比较。实现只使用标准 C++17，不依赖编译器扩展整数类型。
二分维护左端幂不超过目标、右端幂超过目标；初始左端为零，右端为 \(\min(x,16000000)+1\) .直到两端相邻，左端就是 \(r\) .先用上述精确核验可让通常情况避免完整二分，但不改变数学结果。
正确性与整数范围¶
在零处，方程给出 \(F(0)=5F(0)\) ，故 \(F(0)=0\) .对正整数 \(x\) ，两个递归参数 \(\max(r-1,0)\) 和 \(\lfloor x/2\rfloor\) 都小于 \(x\) .按参数归纳，递归调用得到正确值，再代入题设等式就得到正确的 \(F(x)\) ；缓存只复用这个确定值。因此所有查询正确且递归必定终止。
两个子参数都是 \(x\) 的非下降函数，结合递推式可归纳得到 \(F\) 非下降。用精确整数递推计算最大输入得到 \(F(10^9)=12422138161640\) ，也与给定样例一致。因此整个输入范围内的值，以及求和中的非负乘积，都远小于有符号 64 位上限。独立大整数实现核对了这个端点及测试查询。
复杂度¶
用 \(S\) 表示实际展开的不同缓存参数数，\(H\) 表示未缓存参数的展开次数，后者包含重复计算。显然 \(S\le C\) .固定四块与固定指数的整数幂计算是常数次机器整数运算；根查找最坏需要 \(O(\log(U+2))\) 次比较。因此总时间为
若出现未缓存参数，则 \(C=10^7\) .对这个范围内的参数，两种子参数都不超过其一半，因此每次查询在阈值以上展开的二叉树有 \(O(1+U/C)\) 个节点，得到 \(H=O(N(1+U/C))\) 的粗略上界。小于阈值的节点由缓存共享。不要把本算法简写为没有条件的 \(O(N\log U)\) .
数组、查询和栈共占 \(O(C+N+\log(U+2))\) 空间。递归在足够大参数上每层至少减半，小参数段长度有常数上界。最大缓存约占 \(80\) MB，保留原题 \(128\) MB 内存限制。完整表算到最大参数需要过多空间；全参数哈希缓存也没有在该限制下得到更好的可靠方案，因此未另列为优质补充算法。