এই সমস্যাতে, আমাদের চারটি মান A, B, C, M (একটি মৌলিক সংখ্যা) দেওয়া আছে। আমাদের কাজ হলো মডুলো অ্যারিথমেটিক ব্যবহার করে পাওয়ার অফ পাওয়ার (power of power) বের করা।
আমাদের সরাসরি (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) একটি বিশাল সংখ্যা হয়ে যেতে পারে যা স্টোর করা কঠিন এবং ক্যালকুলেশন ওভারফ্লো (overflow) করতে পারে।
তাই একটি দক্ষ পদ্ধতি হলো ফার্মাটস লিটল থিওরেম (Fermat's Little Theorem) ব্যবহার করা।
থিওরেমটি হলো:
a^(m-1) = 1 (mod M) যেখানে m একটি মৌলিক সংখ্যা (prime number)।
এটি ব্যবহার করে আমাদের সমস্যাত bc কে নিচের রূপে রূপান্তর করব:
x*(M-1) + y, আমাদের দেওয়া M-এর জন্য।
ফার্মাটস থিওরেম ব্যবহার করে, A^(x*(M-1)) অংশটি ১ হয়ে যাবে।
এটি ক্যালকুলেশনকে সরল করে দেবে, আমাদের শুধু A^y বের করতে হবে।
y-এর মান বের করা যায়:
B^C = x*(M-1) + y
এটি বোঝায় y হলো B^C কে (M-1) দিয়ে ভাগ করলে বাকি (remainder)।
সুতরাং, 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;
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
