372. Super Pow

• Difficulty: Medium

• Topics: Math

• Similar Questions:

  • Pow(x, n)

Problem:

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3]
Output: 8

Example 2:

Input: a = 2, b = [1,0]
Output: 1024

Solutions:

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        int ret = 1;
        int base = a % MOD; // a need to mod first!
        for (auto it = b.rbegin(); it != b.rend(); ++it) {
            int digit = *it;
            ret = ret * pow(base, digit) % MOD;
            base = pow(base, 10);
        }

        return ret;
    }

private:
    int pow(int val, int n) {
        int ret = 1;
        int power = val;
        for (int i = 0; i < 4; ++i) {
            if ((n >> i) & 1) {
                ret = ret * power % MOD;
            }
            power = (power * power) % MOD;
        }

        return ret;
    }

    static const int MOD = 1337;
};