How to Efficiently Perform Modular Exponentiation

Today, let's discuss a math-related problem, LeetCode #372 "Super Pow," which involves performing large exponentiation and then finding the remainder.

int superPow(int a, int[] b);

int superPow(int a, vector<int>& b);

def superPow(a: int, b: List[int])

func superPow(a int, b []int) int

var superPow = function(a, b) {}

The algorithm you need to implement should return the result of a^b modulo 1337. This means you first calculate the power a^b, but the value of b can be extremely large, so it is represented in the form of an array.

This algorithm is essentially the modular exponentiation algorithm widely used in discrete mathematics. Why we need to take modulo 1337 is not our concern here. For this problem, there are three main challenges:

First, how to handle the exponent represented as an array? Now, b is an array, meaning b can be very large and cannot be directly converted to an integer type, as it might cause overflow. How do you use this array as an exponent in your calculations?

Second, how to get the result after taking the modulo? Ideally, you should first calculate the power and then perform the % 1337 operation. However, as you know, the result of exponentiation can be incredibly large, meaning the actual result cannot be represented and would overflow, causing an error.

Third, how to efficiently perform the exponentiation? There are algorithmic techniques for exponentiation. If you are not familiar with this, it will be explained later in the text.

Let's tackle these issues one by one.