第372题---Super Power

• 题目描述

  • 给定两个数，一个是整数，一个是数组表示很大的整数，求第一个整数的数组的乘方模上1337的结果

• 思路

  • a ^ b % k = a % k ^ b % k % k

• 代码

  class Solution {
  public:
      int powmod(int a, int k) {
          a %= base;
          int result = 1;
          for(int i = 0; i < k; ++i) 
              result = (result * a) % base;
          return result;
      }
  
      int superPow(int a, vector<int>& b) {
          if(b.empty())
              return 1;
          int last_digit = b.back();
          b.pop_back();
          return powmod(superPow(a, b), 10) * powmod(a, last_digit) % base;
      }
      
  private:
      const int base = 1337;
  };