Super Pow trong C ++

Giả sử chúng ta phải tính a ^ b mod 1337 trong đó a là một số nguyên dương và b là một số nguyên dương cực lớn được cho dưới dạng một mảng. Vì vậy, nếu a =2 và b =[1,0] thì đầu ra sẽ là 1024

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định phương thức powerMod (), phương thức này có cơ sở và quyền lực

• m:=1337, ret:=1

• trong khi quyền lực không phải là 0

  • nếu công suất là lẻ, thì ret:=ret * base mod m

  • base:=base ^ 2 mod m

  • power:=power / 2

• trả lại ret

• Xác định superPower (), điều này có a và b

• nếu kích thước của b =0, thì trả về 1

• last:=phần tử cuối cùng của b

• xóa phần tử cuối cùng khỏi b

• return powerMod (superpower (a, b), 10) * powerMod (a, last)) mod 1337

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

2
[1,0]

Đầu ra

1024