문제

문제 링크

어떻게 접근할 것인가?

  • 이 문제는 일단 숫자의 범위가 한정되어 있다는 데서 문제의 접근이 시작된다.
  • 숫자의 범위가 한정되어 있기 때문에 곱셈을 매번해주는 것은 한계가 있다.
  • 미리 문제에서 말했듯이 곱셈을 하고 모드하는 것과 각각을 모드한 다음에 곱셈을 한 결과를 모드한 것이 같다.
  • 때문에 계속해서 곱셈하기 전에 각각을 모드하고 난 후에 결과를 받고 또 모드를 취했다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    unsigned long long answer = 1;
    unsigned long long A, X;
    vector<unsigned long long> v1, v2;
    cin >> A >> X;
    A %= 1000000007;
    while(X != 0){
        if(X%2 == 0) v1.push_back(0);
        else v1.push_back(1);
        X/=2;
    }
    v2.push_back(A);
    for(int i = 1; i < v1.size(); i++){
        unsigned long long temp = (v2[i-1]*v2[i-1])%1000000007;
        v2.push_back(temp);
    }

    for(int i = 0; i < v1.size(); i++){
        if(v1[i] == 1){
            answer *= v2[i]; 
            answer %= 1000000007;
        }
    }
    cout << answer;
}