문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
아이디어
다 곱하는 것이 아니라 나머지를 찾는다는 것에 집중해야 한다.
10 \mod 12 = 10 \\
100 \mod 12 = 4 \\
1000 \mod 12 = 4 \\
10000 \mod 12 = 4
10 \mod 9 = 1 \\
10^2 \mod 9 = 1 \\
10^3 \mod 9 = 1 \\
10^4 \mod 9 = 1 \\
10^5 \mod 9 = 1 \\
코드
python
import sys
input = sys.stdin.readline
a, b, c = map(int, input().split())
def pow(b):
if b == 1:
return a % c
temp = pow(b//2)
if b % 2 == 0:
return temp * temp % c
else:
return temp * temp * a % c
print(pow(b))