[Algo] 분할정복을 이용한 거듭 제곱

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

위 문제의 예제를 보면 10의 11제곱의 결과를 12로 나눈 나머지를 출력하는 문제이다. 그런데 이 숫자들의 범위가 2,147,483,647 이하의 숫자로 매우크다. 최악의 경우 최대값 만큼 제곱을 해야하기 때문에 O(n)으로는 풀 수 없다.

1. 분할정복을 이용한 거듭 제곱

이 알고리즘의 아이디어는 제곱한 결과를 제곱해 나가는 것이다.

(1) 2의 8제곱

2^16 => 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2

• 위와 같이 8번의 연산이 이루어 진다.

(2) 2의 8제곱 (거듭제곱 활용)

2^16 => (((2 ^ 2) ^ 2) ^ 2)

• 위와 같이 제곱의 제곱 즉 거듭제곱을 진행하면 3번의 연산으로 값을 얻을 수 있다.

백준 1629_곱셈 풀이

def power(num, exp, mod):
    if exp == 0:
        return 1
    else :
        x = power(num, exp//2, mod)
        if exp % 2 == 0 :
            return (x * x) % mod
        else :
            return (x * x * num) % mod

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

• 위 식을 참고해서 풀 수 있다.
• 제곱수를 2로 나누었을 때 나머지가 0이면 제곱을 반환
• 제곱수를 2로 나누었을 때 나머지가 있다면 제곱에 * num 을 한번 더 곱한 값을 반환