이 문제는 단순해보이지만 정수론에 관련된 문제로 -> 시간 복잡도, overflow, 홀수 지수에 대한 처리까지 총 3가지 난관이 존재한다.

이때까지 풀었던 문제중에 가장 어려운 문제였다.

사실 이런 문제는 즉석에서 절대 못풀고 O(logN) 시간 복잡도의 빠른 곱셈 코드 블럭 자체를 외우는 수 밖에 없을것 같다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll in_a, in_b, in_c, ret;

ll go(ll a, ll b) {
    if(b == 1) return a % in_c;
    ret = go(a, b/2);
    ret = (ret * ret) % in_c;
    if(b % 2 == 1) ret=ret*(a % in_c) % in_c;
    return ret;
}

int main() {
    cin >> in_a >> in_b >> in_c;
    cout << go(in_a, in_b);
    return 0;
}

2. O(logN)의 빠른 곱셈 코드 블럭

ll go(ll a, ll b) {
    if(b == 1) return a % in_c;
    ret = go(a, b/2);
    ret = (ret * ret) % in_c;
    if(b % 2 == 1) ret=ret*(a % in_c) % in_c;
    return ret;
}

이 코드는 그냥 외워두는게 좋을 것 같다.

만약 문제에서 (a를 b번 곱) % c 를 구하는게 아니라 (a를 b번 곱)만 구하라고 한다면...위의 in_c를 전부 다 제거해주면된다.

ll go(ll a, ll b) {
    if(b == 1) return a;
    ret = go(a, b/2);
    ret = (ret * ret);
    if(b % 2 == 1) ret=ret*a;
    return ret;
}

훨씬 더 간단해진다.

그러나...물론 입력의 범위에따라 달라지겠지만, 대부분의 경우 이렇게만 진행하면 long long 자료형을 쓰더라도 overflow 문제를 피하지 못할 가능성이 매우크다.

3. 배운 점

(1) 재귀 함수에 대한 이해도

이 문제를 풀며 재귀 함수의 동작에 대한 이해도가 확실히 높아졌다.

재귀 함수는 "떡밥을 던지고 회수하는 녀석" 이라는 표현이 맞는진 모르겠지만, 지금은 이렇게 느껴진다.