C++의 슈퍼 파워

a^b mod 1337을 계산해야 한다고 가정합니다. 여기서 a는 하나의 양의 정수이고 b는 배열 형태로 제공된 매우 큰 양의 정수입니다. 따라서 a =2이고 b =[1,0]이면 출력은 1024

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

기본 및 전원을 사용하는 powerMod() 메서드 정의
m :=1337, ret :=1
전력이 0이 아닌 동안
- 전력이 홀수이면 ret :=ret * 기본 모드 m
- 기본 :=기본^2 모드 m
- 전력 :=전력 / 2
리턴 렛
superPower()를 정의합니다. 이것은 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]