Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/372.html

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.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

  • 1 <= a <= 231 - 1
  • 1 <= b.length <= 2000
  • 0 <= b[i] <= 9
  • b does not contain leading zeros.

Algorithm

Related maths

        a^b % 1337 = (a%1337)^b % 1337

        xy % 1337 = ((x%1337) * (y%1337)) % 1337

Reduced by half, the difference is that the remainder of 1337 is added. Since the given exponent b is a representation of a one-dimensional array, it must be very inconvenient to deal with it if we halve it.

So we use bitwise processing, such as 2^23 = (2^2)^10 * 2^3, so we can start from the highest bit of b, calculate a result and store it in res, and then go to the next bit , The tenth power of res is multiplied by the power of a and the remainder is 1337.

Code

  • 
    public class Super_Pow {
    
        class Solution {
    
            // 2^23 = (2^2)^10 * 2^3
            public int superPow(int a, int[] b) {
    
                int res = 1;
                for (int i = 0; i < b.length; ++i) {
                    res = pow(res, 10) * pow(a, b[i]) % 1337;
                }
                return res;
            }
    
            int pow(int x, int n) {
                if (n == 0) return 1;
                if (n == 1) return x % 1337;
                return pow(x % 1337, n / 2) * pow(x % 1337, n - n / 2) % 1337;
            }
        }
    }
    
    ############
    
    class Solution {
        private static final int MOD = 1337;
    
        public int superPow(int a, int[] b) {
            int ans = 1;
            for (int i = b.length - 1; i >= 0; --i) {
                ans = (int) ((long) ans * quickPowAndMod(a, b[i]) % MOD);
                a = quickPowAndMod(a, 10);
            }
            return ans;
        }
    
        private int quickPowAndMod(int a, int b) {
            int ans = 1;
            while (b > 0) {
                if ((b & 1) == 1) {
                    ans = (ans * (a % MOD)) % MOD;
                }
                b >>= 1;
                a = (a % MOD) * (a % MOD) % MOD;
            }
            return ans;
        }
    }
    
  • class Solution:
        def superPow(self, a: int, b: List[int]) -> int:
            MOD = 1337
            ans = 1
            for e in b[::-1]:
                ans = ans * pow(a, e, MOD) % MOD
                a = pow(a, 10, MOD)
            return ans
    
    ############
    
    class Solution(object):
      def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        ret = 1
        k = 1
        for num in reversed(b):
          ret *= a ** (num) % 1337
          a = a ** 10 % 1337
        return ret % 1337
    
    
  • class Solution {
        const int MOD = 1337;
    
    public:
        int superPow(int a, vector<int>& b) {
            int ans = 1;
            for (int i = b.size() - 1; i >= 0; --i) {
                ans = (long) ans * quickPowAndMod(a, b[i]) % MOD;
                a = quickPowAndMod(a, 10);
            }
            return ans;
        }
    
        int quickPowAndMod(int a, int b) {
            int ans = 1;
            while (b) {
                if (b & 1) {
                    ans = (ans * (a % MOD)) % MOD;
                }
                b >>= 1;
                a = ((a % MOD) * (a % MOD)) % MOD;
            }
            return ans;
        }
    };
    
  • const mod = 1337
    
    func superPow(a int, b []int) int {
    	ans := 1
    	for i := len(b) - 1; i >= 0; i-- {
    		ans = ans * quickPowAndMod(a, b[i]) % mod
    		a = quickPowAndMod(a, 10)
    	}
    	return ans
    }
    
    func quickPowAndMod(a, b int) int {
    	ans := 1
    	for b > 0 {
    		if b&1 > 0 {
    			ans = ans * a % mod
    		}
    		b >>= 1
    		a = ((a % mod) * (a % mod)) % mod
    	}
    	return ans
    }
    

All Problems

All Solutions