Trong bài toán này, chúng ta có bốn giá trị A, B, C, M (một số nguyên tố). Nhiệm vụ của chúng ta là Tìm sức mạnh của quyền lực theo mod của một số nguyên tố.
Chúng ta chỉ cần tìm giá trị của (A ^ (B ^ C)) (mod M).
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
A = 3, B = 6, C = 2, M = 11
Đầu ra
3
Giải thích
(A ^ (B ^ C)) =(3 ^ (6 ^ 2)) =(3 ^ (36)) (mod 11) =3
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là bằng cách tính trực tiếp các giá trị của (A ^ (B ^ C)), được thực hiện bằng cách tính giá trị của (B ^ C) trước và sau đó (A ^ (B ^ C)) sau đó lấy mod của nó. (B ^ C) sẽ dẫn đến việc lưu trữ một con số khổng lồ có thể là một nhiệm vụ. Và việc tính toán có thể dẫn đến tràn.
Vì vậy, một cách tiếp cận hiệu quả hơn sẽ là sử dụng Định lý nhỏ của fermat để tìm các giá trị.
Định lý là,
a^(m-1) = 1 (mod M) where m is a prime number.
Sử dụng điều này, chúng tôi sẽ chuyển đổi bc của vấn đề của chúng tôi thành một số dạng,
x * (M-1) + y, với giá trị đã cho của M.
Sử dụng định lý fermat, phần A ^ (x * (M-1)) trở thành 1.
Điều này sẽ làm giảm phép tính, tìm giá trị của A y .
Giá trị của y có thể được tính bằng,
B c =x * (M-1) + y
Điều này làm cho y trở thành phần còn lại khi chúng ta chia B c bởi (M-1),
Vì vậy, y =B c % (M-1)
Điều này làm cho kết quả trở nên dễ dàng như chúng ta cần tìm,
(A ^ ((B^C) %( M-1)) % M
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The power of power under modulo is 3