[백준 1629] 곱셈 (Silver 1)

문제

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

접근

0. a, b를 파라미터로 하는 함수를 만든 뒤 b를 2로 계속 나누어주면서 계속 재귀를 돌린다. 연산 시간을 줄이기 위해 재귀 함수 뒤에 c로 모듈러 연산을 했는데, a % n == a^x % n 의 성질을 이용했다.
1. 제곱근이 홀짝인 경우를 나눈다.
2. 여기서 b가 홀수일 때, a^b // 2 연산을 수행하면 a만큼의 나머지가 항상 남으므로 반환할 때 a를 추가로 곱해준다.
3. 제곱근이 0인 경우에는 a값에 상관없이 항상 1이므로 1을 반환한다. 이 반환식이 재귀 함수에서의 Degenerated Case가 된다.
4. 함수에서 나온 리턴 값에 % c를 나누어 준다.

Code

import sys


def go(a, b):
    if b == 0:
        return 1

    d = go(a, b // 2) % c
    if b % 2 == 1:
        return (d * d * a)
    else:
        return (d * d)


a, b, c = map(int, sys.stdin.readline().split())

answer = go(a, b) % c
print(answer)

여담

3년 전 알고리즘 수업 때 시간에 분할 정복 파트 과제로 나온 문제. 그 때는 어려웠지만, 지금은 풀어버렸다.