[백준/파이썬] 1629번: 곱셈

문제

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

풀이

처음 문제를 접했을 땐 굉장히 단순하게 접근했습니다.

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

하지만 당연하게도 오답..

어떻게 접근해야 될 지 감이 잡히지 않아 구글링을 했습니다.
분할 정복을 통한 제곱수를 구하는 방식을 사용하면 되더군요.

예를 들어, $10^{12}$라면 분배 법칙을 이용해 $10^6*10^6$
즉, $(10^6)^2$로 나타낼 수 있습니다.

이렇게 되면 10을 12번 곱할 것을 10을 6번 곱한 것을 2번 곱하니 12번 수행할 것을 7번만 하면 되니 시간이 굉장히 줄어드는 것을 확인할 수 있습니다.

b가 짝수라면 $a^{b//2} * a^{b//2}$를 하면 되지만 홀수일 경우엔 $a^{b//2} * a^{b//2} * a$까지 해줘야 합니다.

코드

import sys
input = sys.stdin.readline

def func(a,b,c):
    if b == 1:
        return a % c
    tmp = func(a, b//2, c)
    if b % 2 == 0:
        return (tmp * tmp) % c
    else:
        return (tmp * tmp * a) % c

if __name__ == "__main__":
    a,b,c = map(int,input().split())
    print(func(a,b,c))