[BOJ] 곱셈(1629)

[백준(BOJ)] 곱셈(1629) C++

문제 : BOJ_1629번 곱셈

문제 설명

분할정복

A, B, C가 주어지고 , A를 B번 곱한 값을 C로 나눈 값의 나머지를 구하는 문제입니다.

B가 매우 크기 때문에, B에 맞게 여러 번 곱해주면 시간 초과가 납니다.

---

Solution

n이 짝수라면, A^n = A^(n/2) * A^(n/2) n이 홀수라면, A^n = A^(n/2) * A^(n/2) *A인 것을 이용하여 분할 정복 합니다.

값의 크기도 이 문제에서 매우 중요한데, A, B, C의 값이 int형의 최댓값까지 가능하므로, long long형으로 해주고,

mod C를 계속 수행해 주어야 합니다.

그리고 저는 이 문제에서 자꾸 오답 제출이 많이 됐는데, n이 홀수일 때 A^n = A^(n/2) * A^(n/2) *A인 조건에서,

(A^(n/2)*A^(n/2)*A) 를 그대로 묶어서 mod C를 해주면, 세 개의 식이 곱해지는 동안 이미 오버플로우가 발생할 수 있으므로

오답 처리가 됐습니다. ((A^(n/2) _ A^(n/2))%C _ A) % C 와 같은 식으로, 두 수를 먼저 곱하고 mod C를 해주는 것이 중요합니다.

---

Description

1. 문제에 나오는 모든 변수와 함수의 반환값 및 인자를 모두 long long형으로 처리
2. 재귀의 형식으로 곱해지는 횟수가 1일 때까지 내려가는 함수를 사용

---

#include <iostream>
using namespace std;
long long A, B, C;
long long func(long long val, long long num);
// val -> 곱해지는 값, num -> 곱해지는 횟수
int main(void) {
    cin >> A >> B >> C;
    A = A % C;
    long long result = func(A, B) % C;;
    cout << result << '\n';
}
long long func(long long val, long long num) {
    if (num == 1) return val % C;
    long long nowVal = func(val, num / 2) % C;
    if ((num % 2) == 0) return (nowVal * nowVal) % C;
    else return ((nowVal * nowVal % C) * val) % C;
    // 오버플로우를 방지하기 위해 %C를 두 번 해준다.
}