# 如何高效进行模幂运算

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

372. Super Pow | 🟠 |

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.