백준/Silver/1629. 곱셈

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a, b, c;

ll divide(ll a, ll b, ll c) {
    if (b == 1)
        return a % c;

    ll tmp = divide(a, b / 2, c);

    if (b % 2 == 0)
        return (tmp * tmp) % c;
    else
        return ((tmp * tmp % c) * a) % c;

}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> a >> b >> c;

    cout << divide(a, b, c);

    return 0;
}

분할 정복을 이용한 거듭제곱을 사용해야하는 문제
Input이 많기 때문에 일반적인 곱셈을 이용한다면 시간초과가 발생

2^4 -> 2^2 x 2^2
2^8 -> 2^4 x 2^4
위와 같은 방식으로 계산량을 log2로 줄이는 방법임
계산을 64번 해야한다면
64 -> 32 32
32 -> 16 16
16 -> 8 8
8 -> 4 4
4 -> 2 2
2 -> 1 1
위의 과정들은 6번 필요하고, 2^6으로 64번 곱셈해야 할 것을 2^6, 즉 6번으로 줄인 것을 볼 수 있음

하지만 홀수일 때는 a를 다시 한 번 곱해줌으로써 짝수를 맞춰주어야 함
왜냐하면 ll tmp = divide(a, b / 2, c);
위 부분에서 b / 2는 13일 때 6이 되므로 한 번 더 곱해야 원하는 결과를 찾을 수 있음