이 문제에서 우리는 네 개의 값 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이 됩니다.
이렇게 하면 A y 값을 찾는 계산이 줄어듭니다. .
y의 값은 다음과 같이 계산할 수 있습니다.
B ㄷ =x*(M-1) + y
이렇게 하면 B c 를 나눌 때 나머지가 y가 됩니다. (M-1)에 의해,
따라서 y =B c % (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