计算幂的 k 次方模 m

我们的目标是计算幂的 k 次方模 m，其中底数、k 和 m 作为输入提供。

请看上面的图片。您是否尝试过计算这样的问题？让我们试一试。

计算幂的 k 次方，然后求模 m。

解释

在这个问题中，给定 x、k 和 m。计算 ${x^{x{^x{^{^.{^{^.{^{^.}}}}}}}}}$ 直到 k 次，然后求模 m。

让我们用一个例子来理解。

给定，x = 2，k = 4，m = 6

所以，计算 $2^{2^{2{^2}}}\:=\:4^{2{^2}}\:=\:16^2\:=\:256$

然后 256 % 6 = 4。

所以，最终结果是 4。

方法

让我们讨论一下计算幂的 k 次方模 m 的分步算法。

  • 将 x、k 和 m 的值作为输入。

  • 使用 pow 函数计算幂的幂，最后使用模运算符得到最终结果。

  • 打印最终结果作为输出。

计算幂的 k 次方模 m 的 C++ 程序。

#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;
}

输出

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

复杂度

时间复杂度：O(k)，因为这段代码执行了 (k-1) 次迭代。

空间复杂度：O(1)，因为代码使用固定数量的变量来存储输入值和结果，与输入的大小无关。

结论

在本文中，我们试图解释计算幂的 k 次方模 m 的方法，其中底数、k 和 m 的值作为输入给出。我希望本文能帮助您更好地理解这个概念。

更新于： 2023年3月23日

120 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告