C++ এ একটি প্রাইম মোডের অধীনে পাওয়ারের শক্তি খুঁজুন

এই সমস্যায় আমাদের চারটি মান দেওয়া হয়েছে A, B, C, M(a মৌলিক সংখ্যা)। আমাদের কাজ হল প্রাইম মোডের অধীনে পাওয়ারের শক্তি খুঁজে পাওয়া।

আমাদের কেবল (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 ^c =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