数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在 C++ 中求素数模下幂的幂
在这个问题中，我们给出四个值 A、B、C、M（一个素数）。我们的任务是在素数模下求幂的幂。
我们只需要找到 (A ^ (B ^ C)) (mod M) 的值。
让我们来看一个例子来理解这个问题：
输入
A = 3, B = 6, C = 2, M = 11
输出
3
解释
(A ^ (B ^ C)) = (3 ^ (6 ^ 2)) = (3 ^ (36))(mod 11) = 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。
这将计算简化为求 Ay 的值。
y 的值可以计算为：
Bc = x*(M-1) + y
这使得 y 为 Bc 除以 (M-1) 的余数，
所以，y = Bc % (M-1)
这使得结果更容易计算，因为我们需要找到：
(A ^ ((B^C) %( M-1)) % M
程序说明了我们解决方案的工作原理：
示例
#include<iostream>
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<<"The power of power under modulo is "<<findPowerOfPowerMod(A, B, C, M);
return 0;
}输出
The power of power under modulo is 3
更新于：2021年3月16日
502 次浏览
广告