[백준/Python] 1629_곱셈

문제

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

1629번: 곱셈

코드

import sys


def power(a, b):
    if b == 1:
        return a % C
    temp = power(a, b // 2)
    if b % 2 == 0:  # 짝수
        return (temp * temp) % C
    else:  # 홀수
        return (temp * temp * a) % C


A, B, C = map(int, sys.stdin.readline().rstrip().split())
print(power(A, B))

풀이

모듈러 연산은 다음의 3가지 특성을 가집니다.

$$ 1.\ (a + b)\,\bmod\,n = (a\,\bmod\,n + b\,\bmod\,n)\,\bmod\,n $$

$$ 2.\ (a - b)\,\bmod\,n = (a\,\bmod\,n - b\,\bmod\,n)\,\bmod\,n $$

$$ 3.\ (a \times b)\,\bmod\,n = (a\,\bmod\,n \times b\,\bmod\,n)\,\bmod\,n $$

 

모듈러 연산의 특징을 이용하면 거듭제곱의 모듈러 연산을 간단하게 해결할 수 있습니다.

예를 들어 \(10^{7}\,\bmod\,8\)를 구한다면,

$$10^{7}\,\bmod\,8 = (10\,\bmod\,8)^{7}\,\bmod\,8$$

$$ 10\,\bmod\,8 = 2$$

로 거듭제곱을 계산하고 모듈러 연산하는 것보다 빠르고 간단하게 결과를 구할 수 있습니다.

 

코드에서 재귀함수를 이용해서 \(A^B\)를 A로 인수 분해하고 각각의 모듈러를 계산해서 답을 구합니다.