Calculate the power %m of power k

Our goal is to compute k times % m raised to the power, taking as input the base, the values ​​of k and m -

Look at the picture above. Have you tried calculating such a problem? Let's try it.

Calculate the k-th power of the power, and then take the modulo m.

The Chinese translation of

Explanation

is:

Explanation

In this problem, x, k and m are given. Calculate ${x^{x{^x{^{^.{^{^.{^{^.}}}}}}}}}}$, repeat k times, and then take modulo m.

Let us understand through an example.

Known, x = 2, k = 4, m = 6

Therefore, calculate $2^{2^{2{^2}}}\:=\:4^{2{^2}}\:=\:16^2\:=\:256$ p>

Then 256% 6 = 4.

So, the final result is 4.

method

Let us discuss the step-by-step algorithm for computing k times the power of % m.

• Take the values ​​of x, k and m as input.

• Use the pow function to calculate the power of the power, and finally use the modulo operator to get the final result.

• Print the final result as output.

C program calculates the k-th power %m.

#include <iostream>
#include <cmath>
using namespace std;

int powofpow(int x, int k){
   int val = x;
   k--;
   while (k--)
      val = pow(val, x);
 
   return val;
}

int main(){
   int x = 5, k = 2, m = 3;
   int result;
   
   result =  powofpow(x, k);
   result %= m;
   
   cout << "Compute power of power " << k << " times % " << m << " of " << x << " is " << result << endl;
   
   return 0;
}

Output

Compute power of power 2 times % 3 of 5 is 2

Complexity

Time Complexity: O(k) because this code performs iterations (k-1) times.

Space Complexity: O(1) because the code uses a fixed number of variables to store input values ​​and results regardless of the size of the input.

in conclusion

In this article, we try to explain the method of computing the base raised to a power k times modulo m, where the values ​​of the base, k and m are given as input. I hope this article helped you understand this concept better.

The above is the detailed content of Calculate the power %m of power k. For more information, please follow other related articles on the PHP Chinese website!