C++のスーパーパウ

a ^ b mod 1337を計算する必要があるとします。ここで、aは1つの正の整数であり、bは配列の形式で与えられる非常に大きな正の整数です。したがって、a=2およびb=[1,0]の場合、出力は1024

これを解決するには、次の手順に従います-

• これがベースとパワーを取るpowerMod（）メソッドを定義します

• m：=1337、ret：=1

• 電力が0でない間

  • 電力が奇数の場合、ret：=ret * base mod m

  • base：=base ^ 2 mod m

  • パワー：=パワー/ 2

• retを返す

• superPower（）を定義します。これにはaとbが必要です

• bのサイズが0の場合、1を返します

• last：=bの最後の要素

• bから最後の要素を削除する

• return 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