[백준 1629번] 곱셈 풀이

1629번: 곱셈

 

A^B % C 를 구하는 문제이다.

A와 B의 최댓값이 2147483647 이므로, 직접 A^B를 구해 C로 나누면 오버플로우가 발생하게 된다. 

따라서 다음 두가지 사실과 분할 정복 방법을 이용하여 문제를 해결해보고자 한다.

 

1. A^B는 B가 짝수인지 홀수인지에 따라 A^(2/B)의 곱으로 나타낼 수 있다.

 

예를 들어,

B = 10 일 때, A^10 = A^5 * A^5 이다.

B = 9 일 때, A^9 = A^4 * A^4 * A 이다.

 

즉, 

B%2 == 0 (B가 짝수) 일 때, A^B = A^(2/B) * A^(2/B) 가 된다.

B%2 == 1 (B가 홀수) 일 때, A^B = A^(2/B) * A^(2/B) * A 가 된다.

 

2. (M * N) % K 는 (M % K) * (N % K) % K 와 같다.

 

M과 N의 곱을 K로 나눈 나머지는 M을 K로 나눈 나머지와 N을 K로 나눈 나머지를 곱하여 K로 나눈 나머지와 같다.

또한, 세개의 수에 대하여 (M * N * L) % K = ((M % K) * (N % K)) % K * C % K 가 성립한다.

 

두 가지 사실을 조합해보면, 

우리가 구하고자 하는 값은 A^B % C 이다.  이 때, A^B 는 다음과 같으므로,

 

A^B = A^(2/B) * A^(2/B)         (B가 짝수일 때)
    = A^(2/B) * A^(2/B) * A     (B가 홀수 일 때)

 

A^B % C 는 아래와 같이 도출된다.

 

A^B % C

= (B가 짝수 일 때) (A^(2/B) * A^(2/B)) % C = (A^(2/B) % C) * (A^(2/B) % C) % C 
= (B가 홀수 일 때) (A^(2/B) * A^(2/B) * A) % C = (A^(2/B) % C) * (A^(2/B) % C) % C) * A % C

 

solve(int A, int B, int C) 는 A^B % C의 값을 리턴하는 함수이다. 

B == 0 이면 A^B = 1 이므로 A^B % C = 1%C 가 된다.

이외의 경우에는, A^(B/2)%C 의 값을 tmp에 저장해 두고, B가 짝수인지 홀수 인지에 따라 정답을 리턴하면 된다.

 

int solve(int A, int B, int C) {
    
    if (B == 0) return 1%C;
    int tmp = solve(A, B/2, C);
    if (B%2 == 0) return (1LL * tmp * tmp) % C; 
    return (1LL * tmp * tmp) % C * A % C;
}

 

전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int solve(int A, int B, int C) {
    
    if (B == 0) return 1;
    int tmp = solve(A, B/2, C);
    if (B%2 == 0) return (1LL * tmp * tmp) % C; 
    return (1LL * tmp * tmp) % C * A % C;
}

int main() {

    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    printf("%lld", solve(A, B, C));
    return 0;
}