[C++] 곱셈 (백준 1629번)

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

 

#include <iostream>
using namespace std;

long long divpow(long long a, long long b, long long c) {
    if (b == 1) return a % c;
    long long tmp = divpow(a, b / 2, c) % c;
    if (b % 2 == 0) return (tmp * tmp) % c;
    else return (((tmp * tmp) % c) * (a % c)) % c;
}

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

    long long a, b, c;
    cin >> a >> b >> c;

    cout << divpow(a, b, c) << '\n';
}

실제로 곱셈을 b번 진행하면 당연히 시간 초과가 난다. 따라서 분할 정복을 통해 거듭 제곱을 구현해야 한다. 나는 재귀함수를 통해 구현하였다. 그리고 오버플로우가 나지 않도록 중간중간 계속 c를 나눠 주었다. (AC)

 

else return ((a % c) * tmp * tmp) % c;

처음에 이렇게 작성하여 틀렸습니다를 받았다. (WA) 아마도 수를 연속으로 세번 곱하니까 오버플로우가 날 수 있어서 그랬던 것 같다.