After reading this article , You can go and get the following questions ：

**-----------**

Today, let's talk about a topic related to mathematical operations ,LeetCode 372 topic Super Pow, Let you do a huge power operation , Then find the remainder .

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

** Ask your algorithm to return power operations a^b The calculation results of 1337 modulus （mod, That's the remainder ） After the results of the **. You have to calculate the power first

`a^b`

, But this `b`

It will be very big. , therefore `b`

In the form of an array .This algorithm is actually a modular power algorithm widely used in discrete mathematics , As for why we should be right 1337 We don't care , There are three difficulties in this problem alone ：

** One is how to deal with indexes represented by arrays **, Now? `b`

Is an array , in other words `b`

It can be very large , There's no way to go straight to integer , Otherwise, it may overflow . How do you use this array as an index , Do the calculation ？

** The second is how to get the result after module **？ According to the truth , At least we should calculate the result of power operation first , Then I do `% 1337`

This operation . But the problem is , Exponentiation you know , The real results are bound to be terrifying , in other words , There is no way to show the true result , It's a long time ago .

** Third, how to perform power operation efficiently **, There are also algorithmic skills in power operation , If you don't understand the algorithm , I'll explain later .

So for these questions , Let's think separately , Break one by one .

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

### How to deal with array index

** First of all, clarify the problem **： Now? `b`

Is an array , It can't be expressed as an integer , And the characteristic of array is random access , Deleting the last element is more efficient .

Don't consider the requirement of module , With `b = [1,5,6,4]`

For example , The law of exponentiation , We can find such a law ：

See this , Our old readers must have been acutely aware of , This is the sign of recursion ！ Because the scale of the problem has shrunk ：

```
superPow(a, [1,5,6,4])
=> superPow(a, [1,5,6])
```

that , Found this Law , We can simply translate the code framework first ：

```
// Calculation a Of k Result of the power
// We will implement it manually later
int mypow(int a, int k);
int superPow(int a, vector<int>& b) {
// Recursive base case
if (b.empty()) return 1;
// Take out the last number
int last = b.back();
b.pop_back();
// Simplify the original problem , Reduce the scale recursively solve
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// Merge the results
return part1 * part2;
}
```

Come here , It's not hard to understand ！ We have solved `b`

It's an array problem , Now let's see how to deal with mod, Avoid integer overflow caused by too large result .

### How to deal with it mod operation

** First of all, clarify the problem **： Because of the way computers code , Form like `(a * b) % base`

Operations like this , The result of multiplication can lead to overflow , We hope to find a skill , Can simplify this expression , Avoid spillovers and get results .

For example, in binary search , Let's use `(l+r)/2`

Turn it into `l+(r-l)/2`

, Avoid spillovers and get the right results .

that , Let's talk about the technique of modular operation , After all, modular operations are more common in algorithms ：

`(a * b) % k = (a % k)(b % k) % k`

The proof is simple , hypothesis ：

`a = Ak +B;b = Ck + D`

among `A,B,C,D`

It's an arbitrary constant , that ：

`ab = ACk^2 + ADk + BCk +BD`

`ab % k = BD % k`

Again because ：

`a % k = B;b % k = D`

therefore ：

`(a % k)(b % k) % k = BD % k`

Sum up , Then we can get the equation that we simplify the module .

** let me put it another way , Module the result of multiplication , It's equivalent to first modulus every factor , And then we can get the modulus of the result of factor multiplication **.

So extend to this question , To find the power of a number is not to multiply the number ？ So just expand the ideas just now , You can modulo a power operation ：

```
int base = 1337;
// Calculation a Of k Then the power and base The result of module
int mypow(int a, int k) {
// To model a factor
a %= base;
int res = 1;
for (int _ = 0; _ < k; _++) {
// There's multiplication , It's a potential spillover point
res *= a;
// Module the result of multiplication
res %= base;
}
return res;
}
int superPow(int a, vector<int>& b) {
if (b.empty()) return 1;
int last = b.back();
b.pop_back();
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// Modules are required for every multiplication
return (part1 * part2) % base;
}
```

You see ,** First pair factor a modulus , And then every time I do the multiplication res modulus **, This ensures

`res *= a`

When the code is executed, both factors are less than `base`

Of , It will not cause overflow , At the same time, the result is correct .thus , This problem has been completely solved , You can pass LeetCode The question system of .

But some readers may ask , Is this algorithm for power so simple , Direct one for Cycle and multiply ？ Will it be more complicated , Is there a more efficient algorithm ？

There are more efficient algorithms , But in this case alone , That's enough .

Because you think about , call `mypow`

Function passed in `k`

How big... At most ？`k`

But is `b`

A number in an array , That is to say 0 To 9 Between , So it can be said that every call here `mypow`

The complexity of time is O(1). The time complexity of the whole algorithm is O(N),N by `b`

The length of .

But when it comes to power operations , Let's say by the way how to calculate power operation efficiently .

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

### How to find power efficiently

There is more than one algorithm for fast exponentiation , Let's talk about a basic idea we should master . Using the properties of power operation , We can write such a recursion ：

This idea is definitely better than using it directly for It's efficient to find the power of a cycle , Because there is an opportunity to directly scale the problem （`b`

Size ） Cut it in half , The complexity of the algorithm must be log The magnitude of .

Then you can modify the previous `mypow`

function , Translate this recursive formula , Plus the modular operation ：

```
int base = 1337;
int mypow(int a, int k) {
if (k == 0) return 1;
a %= base;
if (k % 2 == 1) {
// k Is odd
return (a * mypow(a, k - 1)) % base;
} else {
// k It's even
int sub = mypow(a, k / 2);
return (sub * sub) % base;
}
}
```

Although for the subject , There is no obvious efficiency improvement in this optimization , But the power algorithm has been upgraded , In the future, if someone asks you to write a power algorithm , At least write the algorithm .

thus ,Super Pow Even if it's completely solved , Including the idea of recursion and the processing of modular operations 、 The skill of power operation , It can be said that this topic is quite interesting , What interesting topic do you have , May as well leave a message to share .

**＿＿＿＿＿＿＿＿＿＿＿＿＿**

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！