문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a,b,c = map(int,input().split())
sum = 0
#memo = {}
def rec(x): #x는 b
if x == 1:
return a%c
else:
tmp = rec(x//2)
if x%2 == 0: #짝수
return (tmp * tmp)%c
else:
return (tmp* tmp *a)%c
sum = rec(b)
print(sum)
a와 b에 너무 큰 수가 들어와서 오버플로우가 생겨도 시간초과가 나므로 미리 c로 나머지를 구한다.
분배법칙에 의해서 다음과 같이 된다.
