거듭제곱의 지수에 집중하자. 점화식을 만들 수 있는 대상이 무엇인지를 찾아보는 것이 최우선이다.
모듈러 연산의 분배법칙과 지수 법칙을 사용할 수 있다.
예시로 나와 있는 (10 ^ 11) % 2를 예로 든다면,
(10 ^ 11) % 2
= ((10^5)%12 x (10^5)%12 x 10)% 12
= ((10^2)%12 x (10^2)%12 x 10) %12 x (10^2)%12 x (10^2)%12 x 10) %12 x 10) %12
로 나타낼 수 있다.
즉, 지수가 짝수이냐 홀수이냐에 따라 지수 N을 반으로 쪼갤 수 있고, 각각을 재귀를 수행하면서 N==1일 때의 리턴값을 받아와 주면 된다.
def recur(n: int, m: int):
if m == 1:
return n % a
temp = recur(n, m//2)
if m % 2 == 0:
return (temp * temp) % a
else:
return (temp * temp * n) % a
n, m, a = map(int, input().split())
recur(n, m)