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.


Example1:

a = 2
b = [3]

Result: 8



Example2:

a = 2
b = [1,0]

Result: 1024



Credits:Special thanks to @Stomach_ache for adding this problem and creating all test cases.

Difficulty: interview

Starter code:

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        

Solutions:
class Solution:
     def superPow(self, a, b):
         result = 1
         fermatb = (int(''.join(map(str, b)))) % 570
         while fermatb:
             if fermatb & 1:
                 result = (result * a) % 1337
             a = (a * a) % 1337
             fermatb >>= 1
         return result

class Solution:
     def superPow(self, a, b):
         return pow(a, int(''.join(map(str, b))), 1337)

class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         
         res = a**b[0]
         for i in range(1, len(b)):
             res = res**10 % 1337 * a**b[i] % 1337 % 1337
         return res

class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         b.reverse()
         p = b.pop()
         res = pow(a,p) % 1337
         while b:
             p = b.pop()
             res = pow(res,10) % 1337
             res = res * pow(a,p) % 1337
         return res


class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         temp1 = a
         temp = 1
         for i in range(len(b)-1,-1,-1):
             if i<len(b)-1:
                 temp1 = pow(temp1,10) % 1337
             temp2 = pow(temp1,b[i]) % 1337
             temp = temp * temp2 % 1337
         return temp


class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         from functools import reduce
         return 0 if a % 1337 == 0 else pow(a, reduce(lambda x, y: (x * 10 + y) % 1140, b) + 1140, 1337)

class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         def eular(mod):
             res, a = mod, mod
             i = 2
             while i * i <= a:
                 if a % i == 0:
                     res = res // i * (i - 1)
                     while a % i == 0:
                         a //= i
                 i += 1
             if a > 1:
                 res = res // a * (a - 1)
             return res
         def qpow(x, n, mod):
             res = 1
             while n > 0:
                 if n&1 != 0:
                     res = res * x % mod
                 x = x * x % mod
                 n >>= 1
             return res
         
         phi = eular(1337)
         n = 0
         for num in b:
             n = (n*10 % phi + num) % phi
         return qpow(a, n, 1337)

class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         a, b = a % 1337, int("".join([str(i) for i in b]))
         base, temp, extra = {1: a}, 1, {a: 1}
         for temp in range(2, 1338):
             rem = base[temp - 1] * a % 1337
             if rem in extra:
                 start = extra[rem]
                 length = temp - start
                 break
             else:
                 base[temp] = rem
                 extra[rem] = temp
         if b in base:
             return base[b]
         return base[start + (b - start) % length]

class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         return pow(a, int(''.join(map(str, b))), 1337)
         # from functools import reduce
         # k=reduce(lambda x,y:x*10+y, b)
         # print(k)
         # return (a%1337)**k


class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         """
         # return pow(a, int(''.join(map(str, b))), 1337)
         from functools import reduce
         k=reduce(lambda x,y:x*10+y, b)
         # print(k)
         # return pow(a,k)%1337
         return pow(a, k, 1337)

class Solution:
     def superPow(self, a, b):
         num = 0
         currentpow = 1
         for item in b[::-1]:
             num += currentpow * item
             currentpow *= 10
         return self.binpow(a, num % 570)
 
     def binpow(self, n, p):
         if(p == 0):
             return 1
         if(p % 2 == 0):
             return (self.binpow(n * n, p // 2)) % 1337
         return (n * self.binpow(n, p - 1)) % 1337

class Solution:
     def superPow(self, a, b):
         """
         :type a: int
         :type b: List[int]
         :rtype: int
         a %= 1337
         if len(b) == 1:
             return self.powMod(a, b[0])
         return self.powMod(self.superPow(a, b[:-1]), 10) * self.powMod(a, b[-1]) % 1337
         """
         res = 1
         x = a % 1337
         for y in b[::-1]:
             res = (res * (x ** y)) % 1337
             x = (x ** 10) % 1337
         return res


class Solution:
     def superPow(self, a, b):
         result = 1
         fermatb = (int(''.join(map(str, b)))) % 570
         while fermatb:
             if fermatb & 1:
                 result = (result * a) % 1337
             a = (a * a) % 1337
             fermatb >>= 1
         return result

class Solution:
     def superPow(self, a, b):
         result = 1
         x = a % 1337
         for y in b[::-1]:
             result = (result * (x**y)) % 1337
             x = (x**10) % 1337
         return result