[백준/Python] 1629번: 곱셈

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

1629번: 곱셈

---

---

문제 분석

 

문제는 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 것이다.

하지만 10의 11 제곱만 하더라도 수가 엄청 커지고 A, B, C의 범위가 상당히 큰 수이므로

직접 제곱수를 구해서 계산할 수 없다.

 

이 때는 분할 정복을 통한 제곱수를 구하는 방식을 사용한다.

분할 정복을 통한 거듭 제곱

위와 같은 식으로 제곱수를 쪼갤 수 있다.

이를 재귀 함수로 작성하여 B가 1이 될 때까지 계산하여 제곱수를 분할해 계산한다.

 

제곱수를 분할했다면 나머지를 구해야 한다.

나머지의 경우는 모듈러 연산의 성질을 통해 쉽게 구할 수 있다.

 

 

모듈러 연산이란?
어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산

모듈러 연산의 나머지 분배 법칙

모듈러 연산은 위와 같은 분배 법칙이 성립한다.

 

덧셈에서의 나머지 분배 법칙을 증명해보자면

A, B 가정

 

위와 같은 A와 B가 있다고 가정하자.

그리고 A와 B를 더하고 C로 나눈 나머지를 구해보자.

 

덧셈에서의 나머지 분배 법칙 증명

 

나머지를 계산한다면 위와 같은 식으로 정리할 수 있다.

즉, 덧셈에서의 나머지 분배 법칙이 성립한다는 것이다.

 

거듭 제곱에서도 마찬가지로 성립한다.

거듭 제곱에서의 나머지 분배 법칙 증명

 

def solution(a, b, c):
    if b == 1:
        return a % c

    temp = solution(a, b // 2, c)

    if b % 2 == 1:
        return ((temp * temp) % c) * a % c
    else:
        return (temp * temp) % c

결론적으로 위와 같은 함수를 작성할 수 있다.

 

---

✏️ 파이썬 내장 함수 활용하기

다른 방식으로는 파이썬 내장 함수를 이용하는 방법이 있다.

 

파이썬은 기본적으로 내장하고 있는 내장 함수가 많이 있다.

여기서 pow()라는 함수를 사용하면 더욱 쉽게 구할 수 있다.

 

파이썬 공식 문서를 통해서 pow 함수에 대해 알아보면

 

pow(base, exp, mod=None)

base의 exp 거듭제곱을 반환합니다. mod가 있는 경우, base의 exp 거듭제곱의 모듈로 mod 를 반환합니다.
pow(base, exp) % mod 보다 더 빠르게 계산됩니다.

두 개의 인자 형식인 pow(base, exp)는 거듭제곱 연산자 base ** exp를 사용하는 것과 동일합니다.

 

이 문제에서는 mod까지 작성하면 쉽게 해결할 수 있다.

 

 

코드

방법 1.

def solution(a, b, c):
    if b == 1:
        return a % c

    temp = solution(a, b // 2, c)

    if b % 2 == 1:
        return ((temp * temp) % c) * a % c
    else:
        return (temp * temp) % c


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

print(solution(a, b, c))

 

방법 2.

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

print(pow(a, b, c))