BAEKJOON 1629 - 곱셈

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

주어진  a, b, c 의 값이 크기 때문에 시간 복잡도를 줄이기 위해 분할 정복을 사용하고, 오버 플로를 방지하기 위해 중간에 얻어지는 값을 c 로 나눠가며 풀어봤습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
ll multiply(ll a, ll b, ll c)
{
    if (b == 0)
        return 1;
 
    int multi = multiply(a, b / 2, c);
    if (b % 2 == 0)
        return multi * multi % c;
    else
        return ((multi * a) % c * multi) % c;
}
 
int main()
{
    ll a, b, c;
    cin >> a >> b >> c;
 
    cout << multiply(a, b, c) % c << endl;
 
    return 0;
}