C++ এ সুপার পাওয়ার

ধরুন আমাদের a^b mod 1337 গণনা করতে হবে যেখানে a হল একটি ধনাত্মক পূর্ণসংখ্যা এবং b হল একটি অ্যারের আকারে দেওয়া একটি অত্যন্ত বড় ধনাত্মক পূর্ণসংখ্যা। সুতরাং a =2 এবং b =[1,0] হলে আউটপুট হবে 1024

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• powerMod() পদ্ধতির সংজ্ঞা দিন এটি বেস এবং পাওয়ার নেয়

• m :=1337, ret :=1

• যখন পাওয়ার 0

  নয়

  • যদি পাওয়ার বিজোড় হয়, তাহলে ret :=ret * base mod m

  • base :=base^2 mod m

  • power :=power / 2

• রিটার্ন রিটার্ন

• সুপার পাওয়ার() সংজ্ঞায়িত করুন, এটি a এবং b

  নেয়

• যদি b =0 এর আকার হয়, তাহলে 1

  ফেরত দিন

• last :=b

  এর শেষ উপাদান

• b

  থেকে শেষ উপাদান মুছুন

• রিটার্ন powerMod(superpower(a, b), 10) * powerMod(a, last)) mod 1337

উদাহরণ(C++)

আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int powerMod(lli base, lli power){
      lli mod = 1337;
      lli ret = 1;
      while(power){
         if(power & 1) ret = (ret * base) % mod;
         base = (base * base) % mod;
         power >>= 1;
      }
      return ret;
   }
   int superPow(int a, vector<int>& b) {
      if(b.size() == 0) return 1;
      int last = b.back();
      b.pop_back();
      return (powerMod(superPow(a, b), 10) * powerMod(a, last)) % 1337;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0};
   cout << (ob.superPow(2, v));
}

ইনপুট

2
[1,0]

আউটপুট

1024