ในปัญหานี้ เราได้รับสี่ค่า A, B, C, M(จำนวนเฉพาะ) งานของเราคือค้นหาพลังแห่งอำนาจภายใต้ mod ของไพรม์
เราแค่ต้องหาค่าของ (A ^ (B ^ C)) (mod M)
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
A = 3, B = 6, C = 2, M = 11
ผลลัพธ์
3
คำอธิบาย
(A ^ (B ^ C)) =(3 ^ (6 ^ 2)) =(3 ^ (36)) (สมัย 11) =3
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือโดยการคำนวณค่าของ (A ^ (B ^ C)) โดยตรง ซึ่งทำได้โดยการคำนวณค่าของ (B^C) ก่อน แล้วจึง (A ^ (B ^ C)) จากนั้น ใช้ mod ของมัน (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 สามารถคำนวณได้ดังนี้
บ ค =x*(M-1) + y
นี่ทำให้ y เหลือเศษเมื่อเราหาร B c โดย (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
