Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: CaldarianX

Problemset: ยกกำลัง

Language: cpp

Time: 0.042 second

Submitted On: 2024-11-20 13:28:36

#include <iostream>

using namespace std;

class Expo{

  public:
    long long int mod;
    int base;
    int power;
    long long int pow[1000000];
    int currentIndex;

    Expo(long long int based,int powered){
      base = based;
      power = powered;
      currentIndex = 0;
      mod = 1000000007;
      pow[0] = based % mod;
    }
    long long int getAnswer(){
      int position = 0;
      long long int answer = 1;
      int temppow = power;
      while(temppow > 0){
        int remain = temppow%2;
        temppow /= 2;
        if(remain == 1){
          answer *= getExpo(position);
          //cout<<getExpo(position)<<" at "<<position<<"\n";
          answer %= mod;
        }
        position += 1;
      }
      return answer;
    }
    long long int getExpo(int x){
      while(x+1 >= currentIndex){
        extendPow();
      }
      return pow[x];
    }
    void debuging(){
      for(int i =0;i<10;i++){
        extendPow();
      }
      for(int i =0;i<10;i++){
        cout<<pow[i]<<" ";
      }
    }
    void extendPow(){
      currentIndex += 1;
      pow[currentIndex] = (pow[currentIndex-1] * pow[currentIndex-1]);
      pow[currentIndex] %= mod;
    }
};


int main(){
  int num;
  cin>>num;
  int pow,base = 0;
  for(int i =0;i<num;i++){
    cin>>base>>pow;
    Expo numx = Expo(base,pow);
    cout<<numx.getAnswer()<<"\n";
  }

}