(BOJ) 1629 풀이

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll pow(ll a,ll x,ll m){
    if(x==1) return a%m;
    ll var=pow(a,x/2,m);
    var=var*var%m;
    if(x%2==0) return var;
    return var*a%m;
}
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    ll A,B,C;
    cin >> A >> B >> C;
    cout << pow(A,B,C);
}

바킹독님의 알고리즘 강의 들으면서 풀어본 문제다.

제귀함수 이용해서 풀 수 있는데, 약간의 수학이 필요했다.

$a^{2n} = a^n*a^n$

$a^1 = a$

$a^n$ 을 알면, $a^{2n}$ 또는 $a^{2n+1}$ 을 O(1) 에 계산할 수 있다.

재귀식은 $a^{x/2}$ 을 구한 뒤, X 가 짝수면 그 값을 제곱한뒤 모듈러 해서 리턴.

홀수면 제곱해서 모듈러 한 값에 a 를 한 번 더 곱해서 모듈러 한 뒤 리턴한다.

이 때 base condition 은 a=1 일 때 a%m 을 리턴하는 것이다.