[C++] BAEKJOON 1629 곱셈

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

1629번: 곱셈

단순히 사칙연산 처럼 보이는 문제입니다. 그렇게 때문에 19년 9월 8일 문제를 푼 시점에 정확도는 25%로 매우 낮지만 정확도 만큼 어려운 문제는 아니었습니다.

분할 정복을 이용한 a^b

[Algorithm] 분할 정복을 이용한 a^b

위 개념을 이용하면 제곱의 복잡도를 O(b) 에서 O(log b) 로 줄여 문제를 해결할 수 있습니다.

#include <iostream>

using namespace std;

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

int main(int argc, const char * argv[]) {
    
    long long a,b,c;
    cin >> a >> b >> c;
    cout << pow(a,b,c) << "\n";

    return 0;
}