BOJ-1629 곱셈

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

문제 소개

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구한다.

문제 풀이

분할 정복을 이용한 거듭제곱을 사용하였다.

a의 n제곱은 아래와 같이 나타낼 수 있다.

\[a ^ n = \begin{cases} 1 & if \;\; n == 0 \\ (a ^ \frac{1}{2}) ^ 2 & if \;\; n > 0 \; and \; n \; even\\ (a ^ \frac{n - 1}{2}) ^ 2 & if \;\; n > 0 \; and \; n \; odd \end{cases}\]

함수 solve는 위 식을 재귀적인 코드로 나타낸 것이다.

재귀 과정 중에 실행 시간을 줄이기 위하여, mod c를 마지막에 하지 않고 함수가 return을 할 때마다 수행해 준다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()


def solve(x, y, z):
    if y == 1:
        return x % z
    # 재귀 호출
    res = solve(x, y // 2, z)
    
    # y가 홀수라면
    if y & 1:
        return res * res * x % z
    # y가 짝수라면
    else:
        return res * res % z


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

참고문헌

https://cp-algorithms.com/algebra/binary-exp.html