LeetCode 372. Super Pow 数学

Super Pow
这道题只要知道

a ^ 666888 = a ^ 666880 * a ^ 8

我们用一个powmod函数可以一边做power运算一遍取膜 🐸

class Solution {
    const int base = 1337;
    int powmod(int a, int b) {
        int result = 1;
        a %= base;
        for (int i = 0; i < b; i++)
            result = (result * a) % base;
        return result;
    }
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        int cur = b.back();
        b.pop_back();
        return powmod(superPow(a, b), 10) * powmod(a, cur) % base;
    }
};