Question

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

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

Example 3:

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

Constraints:

1 <= a <= 2³¹ - 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
}

372 - Super Pow

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions