Leetcode|模幂运算|372. 超级次方

模幂运算求解

• 递归求解用数组表示的指数：a[1,5,6,4]=a4×a[1,5,6,0]=a4×(a[1,5,6])10
• 防止栈溢出的模运算：(a∗b)%k=(a%k)(b%k)%k

代码语言：javascript复制

class Solution {
private:
    int base = 1337;
public:
    int mypow(int a, int k) {
        a %= base;
        int res = 1;
        while(k--) {
            res *= a;
            // 由于(a * b) % k = (a % k)(b % k) % k, 故每次乘法结果均取余base，否则遇大幂会栈溢出
            res %= base;
        }
        return res;
    }

    int superPow(int a, vector<int>& b) {      // eg.a^[1,5,6,4]
        if (b.empty()) return 1;
        int last = b.back();
        b.pop_back();
        int part1 = mypow(a, last);             // a^4
        int part2 = mypow(superPow(a, b), 10);  // (a^[1,5,6])^10
        return part1 * part2 % base;            // 每次乘法结果�se，防止栈溢出，多次取余不影响结果
    }
};

递归 数组

0 人点赞