[백준] 1629 - 곱셈

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

1629번: 곱셈

얼핏 보면 간단해 보이지만 a, b, c의 범위와 시간 제한 때문에 조금 고민이 필요한 문제입니다. 그냥 a^b 를 c로 나누게 되면 b번 반복이 있기 때문에 시간초과가 나게 됩니다. 그렇기에 분할 정복으로 O(b) 를 O(logb) 로 만들어 줍니다. 지수법칙을 적용해 보면 a^b = a^(b/2) * a^(b/2) 로 표현되기 때문에 이를 이용해 재귀를 돌려서 풀어줍니다. 그리고 계산을 하기 전에 a를 미리 c로 나눈값을 대입해 long long 범위 초과가 일어나지 않게 해줍니다. 이가 가능한 이유는 모듈러 연산이 분배법칙을 따르기 때문입니다.

#include <iostream>
using namespace std;
typedef long long ll;

ll a, b, c;

ll f(ll a, ll b, ll c) {
    if (b > 1) {
        ll tmp = f(a, b / 2, c);
        if (b % 2 == 1) return ((tmp * tmp) % c * a) % c;
        else return (tmp * tmp) % c;
    }
    return a;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b >> c;
    a %= c;

    cout << f(a, b, c) << "\n";
    return 0;
}