문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

분할정복 문제다. 문제만 보고 a**b%c 식으로 순진하게 풀었다간 100% 시간초과가 나온다. 어떻게 풀지 몰라서 한참 헤맸다.

핵심은 간단하다. 반으로 쪼개 미리 계산한 다음, 둘을 다시 곱해주면 된다. 이때 b가 중요한데, 홀수냐 짝수냐에 따라 다르다.

• 짝수라면, 반을 나눠 계산한 다음 둘을 곱해주면 된다. 즉 a**(b//2)를 먼저 계산하고, 이를 (a**(b//2))*(a**(b//2)) 식으로 두 번 곱한 다음 %2를 써서 나머지를 구하면 된다.
• 홀수라면, 위와 같이 계산하되 %2를 하기 전에 둘을 곱한 값에 a를 한 번 더 곱해준다.

그러니까, a = 10, b = 10, c = 12라면

((10**5) * (10**5)) % 12

a = 10, b = 11, c = 12라면

((10**5) * (10**5) * 10) % 12

가 된다.

이렇게 함수를 만들어 재귀로 돌며 푸는 것이 핵심.

import sys
a, b, c = map(int, sys.stdin.readline().split())

def power(a, b):
    if b == 1:
        return a%c # b가 1이면 a를 나눈 나머지를 바로 리턴.
    else:
        tmp = power(a, b//2) # a의 (b//2)근을 먼저 구한다.
        if b % 2 == 0: # b가 짝수면
            return (tmp*tmp)%c # tmp를 두 번 곱해주고 c로 나눈 나머지를 반환
        else: # b가 홀수면
            return (tmp*tmp*a)%c # tmp를 두 번 곱한 값에 a를 한 번 더 곱한 다음, c로 나눈 나머지를 반환

print(power(a, b))

[문제 보기]