0372. Super Pow
===============
题目信息
--------
:题号: 0372
:难度: Medium
:主题: 模幂、大指数、十进制数字数组、固定模数
:原题: `LeetCode 0372 `_
:重点: 指数由十进制数字数组表示、不能假设指数可放入普通整数、结果对 ``1337`` 取模
题目重述
--------
给定正整数 ``a`` 和数字数组 ``b``。数组 ``b`` 按从高位到低位保存一个正整数指数,例如 ``[1,0,5]`` 表示指数 ``105``。返回 ``a`` 的该指数次幂除以 ``1337`` 后的余数。
``a`` 位于 ``[1, 2^31-1]``,``b`` 的长度位于 ``[1, 2000]``,每个元素都是 ``0`` 到 ``9`` 的十进制数字。指数可能远超普通整数范围,因此题目契约只提供数字数组,不能依赖先把完整指数转换为固定宽度整数。
自建示例
--------
两位指数:
.. code-block:: text
输入:a = 2,b = [1,1]
输出:711
解释:指数为 11,2^11 = 2048,2048 除以 1337 的余数为 711。
底数可被模数整除:
.. code-block:: text
输入:a = 1337,b = [5]
输出:0
解释:1337 的任意正整数次幂都能被 1337 整除。
按十进制位递推指数
--------------------
若已经处理了指数前缀 ``q``,再读入一位 ``d`` 后新指数是 ``10q + d``,所以
``a^(10q+d) = (a^q)^10 * a^d``。每一步都先把当前结果取十次方,再乘上底数的 ``d`` 次方,并对 1337 取模;整个过程中从未构造完整指数。
模幂函数用二进制快速幂计算小指数 10 或数字位 ``0..9``。底数和中间乘积使用 ``long long``,每次乘法前后都保持在可控范围内。
C++ 实现
--------
.. code-block:: cpp
class Solution {
static constexpr long long MOD = 1337;
long long power(long long base, int exponent) {
long long result = 1;
base %= MOD;
while (exponent > 0) {
if (exponent & 1) result = result * base % MOD;
base = base * base % MOD;
exponent >>= 1;
}
return result;
}
public:
int superPow(int a, std::vector& b) {
long long result = 1;
for (int digit : b) {
result = power(result, 10)
* power(a, digit) % MOD;
}
return static_cast(result);
}
};
代码分析
--------
十进制位递推严格保持了指数的高位到低位顺序,``b`` 再长也只需保存一个模意义下的结果;快速幂则避免逐次相乘。若 ``b`` 长度为 ``L``,每一位只进行常数次模幂,时间复杂度为 ``O(L)``(常数来自最多 4 次平方/乘法),额外空间为 ``O(1)``。