[BOJ 1629] 곱셈

문제링크

소스코드

#include <iostream>

using namespace std;
typedef long long ll;
ll a, b, c;

ll func(ll a, ll b) {
    if (b == 1) {
        return a % c;
    }
    if (b % 2 == 0) {
        ll tmp = func(a, b / 2);
        return (tmp * tmp) % c;
    } else {
        ll tmp1 = func(a, b / 2);
        ll tmp2 = func(a, b / 2 + 1);
        return (tmp1 * tmp2) % c;
    }
}

int main() {
    cin >> a >> b >> c;
    cout << func(a, b) << endl;

}

대표적인 분할정복 문제이다. 재귀함수를 이용하여 거대한 제곱의 형태를 반씩 나누어 게산한다. 아무리 긴 제곱계산도 log2 만큼 줄일 수 있다.
long long을 사용할 때는 typedef를 사용해서 불필요한 타이핑을 줄이도록하자.