LeetCode 372 Super Pow

    
        标签：
        
            数学类题目
        
            LeetCode
        
    发布于：2022-03-01 10:12:59
    编辑于：2022-03-01 10:21:38
    浏览量：890

概述

https://leetcode.com/problems/super-pow/

递归法

https://labuladong.gitee.io/algo/4/30/120/

首先：(a * b) % k = (a % k)(b % k) % k

其次：a ^ mn = (a ^ m) ^ 10 * (a ^ n)

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        int l = myPow(a, b.back()) % 1337;
        b.pop_back();
        int r = myPow(superPow(a, b), 10) % 1337;
        return l * r % 1337;
    }
    
    int myPow(int a, int b) {
        a %= 1337;
        int ans = 1;
        while (b > 0) {
            ans *= a;
            ans %= 1337;
            b --;
        }
        return ans;
    }
};

递归 + 二分求幂

注意处理 b 为 0 的情况，注意每次乘法后都要取余。

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        int l = myPow(a, b.back()) % 1337;
        b.pop_back();
        int r = myPow(superPow(a, b), 10) % 1337;
        return l * r % 1337;
    }
    
    int myPow(int a, int b) {
        if (b == 0) return 1;
        a %= 1337;
        if (b == 1) return a;
        int t = myPow(a, b / 2);
        t *= t;
        t %= 1337;
        if (b % 2 == 1) {
            t *= a;
        }
        return t % 1337;
    }
};

Links: leetcode-372-super-pow