[BOJ] 1629 곱셈

문제 링크

https://www.acmicpc.net/problem/1629

풀이

분할 정복으로 큰 수의 거듭제곱 구하기

문제에서 주어진 A와 B의 범위가 매우 크다. A를 B번 곱하는 다음의 방식으로는 시간 제한을 넘을 수 없다.

pow = 1
for i in range(b):
    pow *= a

빠르게 거듭제곱을 구하기 위해 지수의 덧셈 법칙($a^n \times a^m = a^{n+m}$)을 이용할 수 있다. 덧셈 법칙에 의거하면 다음의 등식이 성립한다. (//는 나머지를 버리는 나눗셈 연산을 뜻한다.)

$a^b$보다 작은 문제인 $a^{(b//2)}$의 값을 구하고, 결과를 제곱하면 훨씬 적은 계산 횟수로 원래 풀려던 문제의 답을 구할 수 있다. 이런 문제 해결 패턴을 분할 정복이라 한다.

분할 정복을 통해 거듭제곱을 구하는 과정을 파이썬 코드로 표현하면 다음과 같다.

def pow(base:int, exponent:int):
    if exponent == 1:
        return base

    half = pow(base, exponent // 2)

    ret = half * half
    if (exponent % 2) != 0:
        ret *= base

    return ret

나머지 연산의 분배 법칙을 이용해 결과가 큰 곱셈의 나머지 구하기

문제에서 원하는 것은 $a^b$가 아니라 $a^b \bmod c$ 이다. 파이썬은 오버플로우를 자동으로 예방해주는 언어이므로 다음과 같이 작성하여도 답은 맞게 나올 것이다.

def solve2(a:int, b:int, c:int):
    return pow(a, b) % c

그러나 위 코드는 시간 초과로 통과할 수 없다. 설령 시간 제한에 걸리지 않는다 하더라도 출제자가 파놓은 정수 오버플로우의 함정을 이런식으로 지나치는 건 어딘지 아쉽다. 오버플로우가 일어나지 않도록 하기 위해 나머지 연산의 곱셈 분배법칙을 이용할 수 있다. 나머지 연산의 곱셈 분배법칙이란 다음 등식이 성립함을 말한다.

위 법칙을 증명해보자. a를 c로 나눈 몫을 q1, 나머지를 r1이라 하고 b를 c로 나눈 몫을 q2, 나머지를 q2라 하면 다음의 등식이 성립한다.

위 등식을 이용해 $(a \times{b})\bmod {c}$를 전개하면 다음과 같다. 이를 1번 연산이라 하자.

수행하는 연산이 나머지 연산이라는 점에 주목하자. c로 묶인 부분은 $(a \times b)\div c$ 의 몫이므로 나머지 연산의 결과에서 제거된다. 따라서 1번 연산의 결과는 $r_1r_2$이다.

같은 방식을 이용해 $\{(a \bmod c){\times}(b \bmod c)\} \bmod c$을 전개하면 다음과 같다. 이를 2번 연산이라 하자.

1번 연산에서 $r_1r_2$는 $(a \times b)\div c$의 나머지였으므로 $r_1r_2 < c$ 이다. 따라서 $r_1r_2 \bmod c = r_1r_2$ 이다. 1번 연산과 2번 연산의 결과가 같음을 보였으므로 나머지 연산의 곱셈 분배 법칙은 성립한다.

나머지 연산의 곱셈 분배법칙으로 $a^b \bmod c$를 구하는 과정을 파이썬 코드로 표현하면 다음과 같다.

# get (a * b) mod c by Distributive property
def mod_of_multiple(a:int, b:int, c:int):
    return ((a % c) * (b % c)) % c

코드(python3)

분할정복을 이용해 거듭제곱을 계산하는 알고리즘과, 나머지 연산의 분배법칙을 결합하면 다음과 같이 답을 구할 수 있다.

# get (a * b) mod c by Distributive property
def mod_of_multiple(a:int, b:int, c:int):
    return ((a % c) * (b % c)) % c

def solve(a:int, b:int, c:int):
    if b == 1:
        return a % c

    #get a^(b//2) % c
    half = solve(a, b // 2, c)
    ret = mod_of_multiple(half, half, c)

    if (b % 2) != 0:
        ret = mod_of_multiple(ret, a, c)

    return ret

a, b, c = map(int, input().split())
print(solve(a, b, c))