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 }