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 的十进制数字。指数可能远超普通整数范围,因此题目契约只提供数字数组,不能依赖先把完整指数转换为固定宽度整数。

自建示例

两位指数:

输入:a = 2,b = [1,1]
输出:711
解释:指数为 11,2^11 = 2048,2048 除以 1337 的余数为 711。

底数可被模数整除:

输入: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++ 实现

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<int>& b) {
        long long result = 1;
        for (int digit : b) {
            result = power(result, 10)
                   * power(a, digit) % MOD;
        }
        return static_cast<int>(result);
    }
};

代码分析

十进制位递推严格保持了指数的高位到低位顺序,b 再长也只需保存一个模意义下的结果;快速幂则避免逐次相乘。若 b 长度为 L,每一位只进行常数次模幂,时间复杂度为 O(L)``(常数来自最多 4 次平方/乘法),额外空间为 ``O(1)。