Baekjoon 1629번 곱셈

문제

https://www.acmicpc.net/problem/1629

걸린 시간

02 : 13 : 13 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll power(ll x, ll n, ll mod){
    // 기저 사례
    if(n == 0) return 1;
    // 재귀 호출
    ll ret;
    if(n%2 == 0) ret = power(x*x%mod, n/2, mod);
    else ret = x*power(x*x%mod, (n-1)/2, mod);
    return ret%mod;
}

int main(){
    fastio;
    ll a, b, c;
    cin >> a >> b >> c;
    cout << power(a, b, c);
    return 0;
}

제수에 따라 나머지 값이 일정한 규칙을 가지는 것을 보고 반복되는 규칙을 찾아 시간복잡도를 줄이려고 했었다. 하지만 규칙이 분명하게 보이지 않았고 2시간을 고민하다 결국 답을 보았는데, 거듭제곱을 재귀를 이용해 logN 만에 구할 수 있는 방법이 존재했다. 더 충격적인 것은 알고리즘을 처음 공부할 때 직접 포스팅까지 했었던 개념이었다.