백준[1629] - 곱셉

문제

백준 1629 문제 보기

접근 방법

모듈러의 분배 법칙을 이용하면 문제를 쉽게 풀수 있을것 같았다. 하지만 A와 B의 범위가 너무 커 O(N)으로 풀기에는 역부족이다. 따라서 지수 법칙을 같이 이용하여 O(logN)으로 문제를 해결했다.

• 지수가 짝수 : B/2로 분할 정복
• 지수가 홀수 : B-1로 분할 정복

코드

#include <iostream>
using namespace std;

long long A, B, C;

long long cal(long long A, long long B) {
    if(B == 0) return 1;
    if(B == 1) return A % C;
    if(B % 2 == 0) {
        long long temp = cal(A, B / 2);
        return (temp * temp) % C;
    } else {
        return (A * cal(A, B - 1) % C);
    }
}

int main() {
    cin >> A >> B >> C;
    cout << cal(A, B) << endl;
    return 0;
}