[백준 2024/09/10] 1629번 곱셈

1. 문제

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

 

2. 접근 방법

처음엔, 패턴을 찾아서 돌리는 방법으로 코드를 구현했었다.

하지만, 가차없이 시간 초과가 떴고 다른 방법을 찾다가 '빠른 거듭제곱의 알고리즘' 에 대해서 알게 되었다.

이는 분할 정복을 이용한 것이다.

a^13의 경우 a^12 * a 와 동일하다

또한 a^12의 경우 

half = a^6 일 때, half * half와 동일하다.

따라서 이를 이용해서, 재귀를 구현하면서 분할 정복이 가능해 지는 것이다.

 

3. 코드

from collections import defaultdict
import sys


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

    elif b % 2 == 0:
        half = remainder(a, b//2, c)
        return (half * half) % c

    else:
        return (a * remainder(a, b-1, c)) % c


if __name__ == "__main__":
    a, b, c = map(int, sys.stdin.readline().split())
    print(remainder(a, b, c))