[백준] 곱셈

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

1629번: 곱셈

분할정복을 이용하는 문제입니다. 

 

문제부터 요약하면, A, B, C 가 주어질 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력해야 합니다. 

 

<Solution>

예전에 

https://life318.tistory.com/22

[백준] 이항 계수 3(페르마 소정리, modular inverse, 분할정복)

위의 문제를 해결하는 중 분할정복하여 거듭제곱을 구하는 함수를 만들어 두었기에 그대로 활용하여 해결하였습니다.

 

실제 구현은 아래와 같습니다.

import sys

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

def exp(base: int, expo: int) -> int:
    if expo == 1:
        return base % C
    a = exp(base, expo//2)
    b = expo%2
    # print(f'a,b = {a,b}')
    return a*a*(base**b) %C

print(exp(A,B))