微客导航 » 文章资讯 » 在 C++ 中求素数模下的幂次方

在 C++ 中求素数模下的幂次方

2023-06-16 12:19:03 183

在这个问题中，我们给出了四个值A、B、C、M(aprimenumber)...。我们的任务是在素数的mod下找到幂的幂。

我们只需要找到(A^(B^C))(modM)的值。

让我们举个例子来理解这个问题，

输入

A = 3, B = 6, C = 2, M = 11

输出结果

解释

(A^(B^C))=(3^(6^2))=(3^(36))(mod11)=3

解决方法

该问题的一个简单解决方案是直接计算(A^(B^C))的值，首先计算(B^C)的值，然后(A^(B^C))然后采取其模式。(B^C)将导致一个巨大的数字存储，这可能是一项任务。并且计算可能会导致溢出。

因此，更有效的方法是使用费马小定理来查找值。

定理是，

a^(m-1) = 1 (mod M) where m is a prime number.

使用它，我们将把问题的bc转换为多种形式，

x*(M-1)+y，对于我们给定的M值。

使用费马定理，部分A^(x*(M-1))变为1。

这将减少计算，找到A^y的值。

y的值可以计算为，

B^c=x*(M-1)+y

这使得y成为我们将B^c除以(M-1)时的余数，

所以，y=B^c%(M-1)

这使得结果很容易，因为我们需要找到，

(A ^ ((B^C) %( M-1)) % M

程序来说明我们的解决方案的工作，

示例

#include
using namespace std;
int calcPowerMod(int x, int y, int p) {
   int powMod = 1;
   x = x % p;
   while (y > 0) {
      if (y & 1)
         powMod = (powMod*x) % p;
      y /=2; //y=y/2
      x = (x*x) % p;
   }
   return powMod;
}
int findPowerOfPowerMod(int A, int B, int C, int M) {
   return calcPowerMod(A, calcPowerMod(B, C, M-1), M);
}
int main() {
   int A = 3, B = 6, C = 2, M = 11;
   cout<<"模下幂的幂是 "<输出结果模下幂的幂是 3

返回顶部
3162201930
czq8825@qq.com

在 C++ 中求素数模下的幂次方

输入

解释

解决方法

示例

热门推荐

随机推荐