[백준] 1629번 : 곱셈

문제

 

---

풀이

 

거듭제곱 계산 문제는 유명한 분할 정복 문제이다.

A^B가 있을 때 이 문제를 어떻게 나눌 수 있을까?

 

B가 짝수일 때

A^B = A^(B/2) * A^(B/2) 

 

B가 홀수일 때

A^B = A * A^(B-1)

 

종료조건은 사람마다 B가 0일때 하거나 1일때 하거나 하던데 난 그냥 1로 했다.

---

소스코드

 

#include <iostream>

using namespace std;

typedef long long ll;

ll divide(ll A, ll B, ll C) {
    ll tmp;

    if (B == 1) //더이상 나눌 수 없음
        return A % C;
    else {
        if (B % 2 == 0) { //짝수 거듭제곱일 때
            tmp = divide(A, B / 2, C);
            return (tmp * tmp) % C;
        } else //홀수 거듭제곱일 때
            return (A * divide(A, B - 1, C)) % C;
    }
}

int main() {
    ll A, B, C;

    cin >> A >> B >> C;
    cout << divide(A, B, C);
}

전체 소스코드다.

 

typedef long long ll;

long long을 하나하나 타이핑하는건 너무 귀찮아서 typedef 해줬다.

 

ll divide(ll A, ll B, ll C) {
    ll tmp;

    if (B == 1) //더이상 나눌 수 없음
        return A % C;
    else {
        if (B % 2 == 0) { //짝수 거듭제곱일 때
            tmp = divide(A, B / 2, C);
            return (tmp * tmp) % C;
        } else //홀수 거듭제곱일 때
            return (A * divide(A, B - 1, C)) % C;
    }
}

B==1일 때는 A^1이란 뜻이니까 A를 C로 나눈 나머지를 리턴한다.

B가 짝수일 때는 B를 2로 나눈 값을 재귀로 호출해 tmp에 담은 뒤, tmp의 제곱을 C로 나눈 나머지를 리턴한다.

B가 홀수일 때는 A와 A^(B-1)을 곱하고 이를 C로 나눈 나머지를 리턴한다.

 

처음엔 제곱을 할 때 pow함수를 사용했는데 이 함수의 리턴형이 double인지라 제대로 계산이 되지 않아 그냥 수동으로 곱했다.