Share my C++ solution with a brief explanation, easy to understand


  • 1
    V

    a ^ b = a ^ (b1 * 10 + c)
    = (a ^ c) * (a ^ (10 * b1))
    = (a ^ c) * ((a ^ 10) ^ b1)


    c = 2 ^ x1 + 2 ^ x2 +...... 2 ^ xn, xi = 0 or 1
    a ^ c = (a * a)^x1 * (a * a)^x2 * ...... * (a * a)^xn


    class Solution {
    public:
        const int MOD = 1337;
    
        int superPow(int a, vector<int>& b) {
            int n = b.size();
            int ret = 1;
            
            for (int i = n-1; i >= 0; i--)
            {
                ret = ret * pow_help(a, b[i]) % MOD;
                a = pow_help(a, 10);
            }
            
            return ret;
        }
        
        int pow_help(int a, int b)
        {
            int ret = 1;
            a %= MOD;
            
            while (b > 0)
            {
                if (b & 1)
                    ret = ret * a % MOD;
                
                b >>= 1;
                a = a * a % MOD;
            }
            
            return ret;
        }
    };
    

  • 0
    V

    another approach, but time limit exceeded

        int superPow(int a, vector<int>& b) {
            int n = b.size();
            const int MOD = 1337;
            int ret = 1;
            bool is_odd = false;
            
            if (is_zero(b))
                return 1;
            
            a = a % MOD;
            
            if (b[n-1] % 2 == 1)
                is_odd = true;
            
            divide_two(b);
            ret = superPow(a, b) % MOD;
            ret = (ret * ret) % MOD;
    
            if (is_odd)
                ret = (ret * a) % MOD;
    
            return ret;
        }
        
        void divide_two(vector<int> &b)
        {
            int n = b.size();
            int remainder = 0;
            
            for (int i = 0; i < n; i++)
            {
                b[i] += 10 * remainder;
                remainder = b[i] % 2;
                b[i] /= 2;
            }
        }
        
        bool is_zero(vector<int> &b)
        {
            int n = b.size();
            
            for (int i = 0; i < n; i++)
            {
                if (b[i] > 0)
                    return false;
            }
            
            return true;
        }
    

Log in to reply
 

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