백준 1629 - 곱셈 [Python]

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

1629번: 곱셈

---

풀이 과정

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

 

A, B, C 모두 약 21억까지 수가 들어올 수 있는데 시간제한이 0.5초다. 반복문으로 A를 21억번 곱하는 방법으로 풀면 O(N)으로 시간 초과가 발생하게 된다.

 

2의 32승은 2의 16승 * 2의 16승과 같다. 이러한 지수 법칙을 이용하면 계산의 시간복잡도를 O(logN)으로 바꾸어 문제를 해결할 수 있다.

 

A*B % C = ((A%C) * (B%C)) % C 임을 이용해 오버플로우가 나지 않도록 계산을 진행하여야 한다.

---

소스 코드

import sys


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

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

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


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