[백준] 1629번 (python 파이썬)

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

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

 

A, B, C는 모두 2,147,483,647 이하의 자연수다. 즉 반복문으로는 절대 풀수없다.

 

때문에 분할 정복을 선택하였다.

첫 풀이

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


def dnc(length):
    if length == 1:
        return a 
    if length % 2 == 0:
        left = dnc(length // 2)
        return left * left 
    else:
        left = dnc(length // 2)
        return left * left * a 


print(dnc(b))

 

이렇게 푸니까 시간초과가 나왔다..

 

검색해보니 오버플로우도 시간초과가 나온다고 한다.???음?

 

생각해보니 a, b모두 엄청 큰 숫자가 들어오면 변수에 담을 수 없다고 생각했다.

 

그래서 매번 연산마다 %c 연산을 해준다.

분배법칙을 보면 결국 같은 것을 알 수 있다.

 

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


def dnc(length):
    if length == 1:
        return a % c
    if length % 2 == 0:
        left = dnc(length // 2)
        return left * left % c
    else:
        left = dnc(length // 2)
        return left * left * a % c


print(dnc(b))