[백준 1629] 곱셈 [C]

백준 - 1629

---

풀이

분할 정복을 이용한 거듭제곱 알고리즘의 기초적인 방법으로 풀이했다.

입력된 수는 int형으로 충분히 담아낼 수 있지만, 두 수의 곱은 이를 벗어나기 때문에, long long형으로 담아주어야 한다.

Test Case에 주어지는 C의 값은 결과를 int형으로 출력할 수 있게 주어지는 듯 했다. 착한 문제지 쉬운 문제는 아니다.

홀수의 경우에는 A를 한번 더 곱해서 맞춰주어야 하므로 (B%2 ? A : 1) 으로 해결했다.

---

소스코드

#include <stdio.h>
long long mul(int A, int B, int C) {
    if (B > 1) {
        long long temp = mul(A, B/2, C);
        return ((temp*temp)%C * (B%2 ? A : 1)) % C;
    } else return A;
}
int main() {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    printf("%d\n", mul(A % C, B, C));
}

---

출처

1629번: 곱셈