# How to carry out modular power operation efficiently

2020-11-09 19:33:30

372. Super power

-----------

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 ！