[백준][C++] 1629: 곱셈 (d-q)

문제

1629: 곱셈

풀이

• 유명한 분할 정복을 이용한 거듭제곱문제

  $a^4 = a^2 * a^2$

  $a^3 = a^2 * a$

• 위 식을 토대로 코드를 짜면된다.

코드

#include <iostream>

using namespace std;

long long fast(int a, int n, int c) {
    if(n == 0) {
        return 1;
    }
    if(n%2 == 0) {
        long long tmp =  fast(a, n/2, c)%c;
        return (tmp*tmp)%c;
    }
    else {
        return (fast(a, n-1, c)*a)%c;
    }
}

int main() {
    int a, b, c;
    cin>>a>>b>>c;
    cout<<fast(a,b,c);
}

반성

• 기저조건 n == 0일 경우를 깜빡하였다.

• 기저조건을 항상 먼저 체크하자