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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Divide and conquer

Mathematics

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):
		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):
		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):
		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):
		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):

		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):
		(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):
		from functools import reduce
		k = reduce(lambda x, y: x * 10 + y, b)
		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):
		res = 1
		x = a % 1337
		for y in b[::-1]:
			res = res * x ** y % 1337
			x = x ** 10 % 1337
		return res