c++-Based on 'Group-theory' and 'fast exponentiation'-0ms


  • 1
    E
    class Solution {
    public:
        int superPow(int a, vector<int>& b) {
            a = a % 1337;
            int ord = 6*190, expo = 0, res = 1;
            // 1337 = 7 * 191, ord(1337) = (7-1)*(191-1) => a^k = a^(k mod 6*190)
            for(int x:b) expo = (10 * expo + x) % ord;
            // fast exponentiation: see exponent as binary,a^b = a^b0 * (a^2)^b1 * (a^4)^b2 ....
            for(int m=1; m<expo; m*=2){
                if(expo & m) res = (res*a) % 1337;
                a = (a*a) % 1337;
            }
            return res;
        }
    };
    

  • 0

    Clean and nice solution, but your code will return wrong answer when expo is the power of 2. The condition of the second for loop should be "m <= expo".


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.