백준_1629_곱셈

문제

1629번: 곱셈

풀이

A, B가 커짐에 따라 A**B의 수행시간이 늘어난다. 따라서 이문제는 분할 정복을 이용하여 해결해야 한다. 모듈러 연산의 성질과 분할정복을 이용하면 B번의 연산을 log2B번으로 줄일 수 있다.

코드

def f(A, B) :
    if B==0 : return 1
    if B%2==0 :
        tmp1 = f(A, int(B / 2))
        ans = (tmp1 * tmp1) % C
    else :
        tmp1 = f(A, int(B / 2))
        tmp2 = (tmp1 * (A % C)) % C
        ans = (tmp1 * tmp2) % C
    return ans

A, B, C = map(int, input().split())
ans = f(A, B)
print(ans)

알고리즘

분할 정복 알고리즘: 문제를 작은 문제로 분할하여 문제를 해결하는 방법

분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전