Baekjoon 1629 (곱셈)

Baekjoon 1629, 백준 1629 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <iostream>
using namespace std;

long long multiply_split(long long a, long long b, long long c) {  // a^b = ? (mod c)
    if(b == 0) return 1;

    if(b%2 == 1) return ((a%c) * (multiply_split(a, b/2, c)) % c * (multiply_split(a, b/2, c) % c)) % c;
    else return ((multiply_split(a, b/2, c) % c) * (multiply_split(a, b/2, c) % c)) % c;
}

int main() {
    long long A, B, C;
    cin >> A >> B >> C;
    cout << multiply_split(A, B, C) << '\n';
}

문제 보고 바로 분할정복이 (다행히) 떠오른 케이스.
a^b = ? (mod c) 를 구하는 문제인데, b를 홀 짝으로 나누어 절반씩 분할정복하면 된다.
생각보다 % c 를 곳곳에 써주어야 해서 쓸데없이 많이 틀렸던 문제.