372 Super Pow

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

a = 2
b = [3]
Result: 8

Example2:

a = 2
b = [1,0]
Result: 1024

Solution

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        // mod 1337
        a = a%1337;
        vector<int> res(1, 1);
        unordered_map<int, int> map;
        map[1] = 0;
        int istart;
        while ( true ) {
            int next = (res[res.size()-1]*a)%1337;
            if ( map.find(next) != map.end() ) {
                istart = map[next];
                break;
            }
            res.push_back(next);
            map[next] = int(res.size())-1;
        }
        int n = res.size() - istart, nb = b.size(), count = 0;
        for ( int i = 0; i < nb; i++ ) count = (count*10 + b[i])%n;
        return res[count];
    }
};

Notes
这题思路很明确，但是需要注意几个细节：

• a = a%1337防止溢出
• 余数循环不一定是从1开始，所以需要一个额外的map记录出现过的余数，寻找循环开始的地方。
• res.size()-istart为循环周期。