資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告