[백준 1629] 곱셈 (C++)

이 문제는 단순히 누적해 곱해나가는 방식으로는 시간초과가 발생한다. 이유는 컴퓨터는 대략 1초에 3~5억번의 연산이 가능한데 (다만, 보수적으로 잡으면 1억번) 최악의 경우 곱셈만 20억번 넘게 하게되므로 무조건 시간초과가 발생하는 것이다.

따라서, $O(N)$의 시간복잡도일 경우 문제가 생기므로, $O(logN)$의 시간복잡도로 문제를 해결해야한다.

이를 바탕으로, 재귀를 통해 반 term씩 분할하며 해결해나가면 로그스케일로 해결할 수 있다는 것을 알 수 있다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll a, b, c;

ll solve(ll x, ll y, ll z) {
    if (y == 0) return 1;
    ll temp = solve(x, y / 2, z);
    temp = temp * temp % z;
    if (y % 2) temp = temp * x % z;
    return temp;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> a >> b >> c;
    cout << solve(a, b, c);
}

다만, a * a는 int형의 최대 표현 범위를 벗어날 수 있으니 long long으로 다루는 것이 안전하다는 것을 유의하자.