백준 / 1629 / 곱셈 / C++

문제 링크 : https://www.acmicpc.net/problem/1629

#include <bits/stdc++.h>

using namespace std;

long long int a, b, c;
unordered_map<int, long long int> dp;

long long int func(int val)
{
    if (dp.find(val) != dp.end())
    {
        return dp[val];
    }

    if (val == 1)
    {
        return dp[val] = a % c;
    }

    long long int tmpval = func(val / 2);
    long long int result;

    if (val % 2 == 0)
    {
        result = tmpval * tmpval % c;
    }
    else
    {
        result = tmpval * tmpval % c * a % c;
    }

    return dp[val] = result;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    
    cin >> a >> b >> c;

    cout << func(b) << endl;

    return 0;
}

입력 크기가 어마어마해서 시간복잡도를 첫 시도에 최대한 줄이려고 많은 기법을 넣어보려 했다. 우선 일반적 거듭제곱(O(N)) 이 아닌 분할정복 재귀를 이용한 거듭제곱(O(log N)) 을 사용했고, 사용한 값은 다시 활용할 수 있도록 DP도 사용했지만... 풀고 나서 다른 분들의 블로그를 보니 DP를 사용할 필요는 없었던 것 같다.