[python] 백준 1629번 - 곱셈

A^B%C를 구하는 문제.

단순하게 쓰면 시간초과가 난다.

 

이 문제를 풀기 위해서는 두 가지의 개념을 알아야 한다.

 

분할정복(Divide and Conquer)을 활용한 거듭제곱

분할정복을 사용하면 거듭제곱을 빠르게 할 수 있다.

보통의 거듭제곱은 x를 n번 곱하기 때문에 시간복잡도가 O(N)이 된다.

 

하지만 다음과 같은 식을 통해 분할정복을 사용한다면 O(logN)으로 거듭제곱을 할 수 있다.

다음은 이 식을 구현한 코드이자 이 문제의 정답이다,

import sys
input = sys.stdin.readline

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

def pow(a, b):
    if b == 0:
        return 1
    tmp = pow(a, b // 2)
    if b % 2 == 0:
        return (tmp * tmp) % C
    else:
        return (tmp * tmp * a) % C
    
print(pow(A, B))

b가 0일때, 더 이상 쪼갤 수 없으므로 1을 리턴한다.

b가 짝수라면 짝수일 때 식, b가 홀수라면 홀수일 때 식을 계산해서 리턴한다.

 

근데 자세히 보면 리턴할 때 C를 나눈 나머지를 반환하는 것을 볼 수 있다.

이에 대한 이유는 다음과 같다.

 

나머지 연산 분배법칙

보통의 알고리즘 문제에서 결과의 값이 매우 큰 경우, 그 값의 나머지를 구하라는 지시가 자주 등장한다.

하지만 매우 큰 값에 나머지를 구하는 연산을 취하는 것은 이미 오버플로우가

발생한 상태에서 연산을 하는 것이기 때문에 연산 과정 중간에 나머지 연산을 해주어야 한다.

 

연산 과정 중간에 나머지 연산을 해주기 위해서는 나머지 연산 분배법칙을 알아야 한다.

그 식은 다음과 같다.

(A + B) % p = (A % p + B % p) % C
(A - B) % p = (A % p - B % p) % C
(A * B) % p = (A % p * B % p) % C

나누기의 경우는 적용되지 않는다.

페르마의 소정리? 를 사용해야 한다고 한다..