📝핵심개념

지수의 성질을 이용한 분할 정복과 나머지(Modulo) 연산자의 분배 법칙을 이용해야 한다.

A와 B값에 들어갈 수 있는 수는 21억 가량 되기 때문에 A^B를 직접 계산해서 문제를 해결할 수는 없다. 따라서 A^B를 분할해야 한다.
만약 B가 짝수이면 예를 들어 2^10이 주어졌다고 하면 2^10 = (2^5)X(2^5)으로 나눌 수 있다. (중학교 때 배우는 지수 법칙)
만약 B가 홀수라면 2^5 = 2X(2^2)X(2^2)로 표현할 수 있다. 이를 이용해 지수가 1이 될때까지 분할 정복을 이용하면 O(logn)시간만에 A^B의 값을 구할 수 있다.

💡 나머지(Modulo) 연산자 분배법칙

(A + B) % C = ((A % C) + (B % C)) % C
(A X B) % C = ((A % C) X (B % C)) % C
(A - B) % C = ((A % C) - (B % C) + C) % C

뺄셈의 경우 음수가 나오는 것을 방지하기 위해 +C를 추가적으로 해준다.

💻 소스코드

import sys
input = sys.stdin.readline

# A, B, C를 입력받는다.
A, B, C = map(int, input().split())

def func(A, B):
    # 만약 B가 1이라면 A%C를 출력
    if B==1:
        return A%C
    else:
        # 원래 지수의 절반을 이용해 temp를 구한다.
        temp = func(A, B//2)
        # 만약 B가 짝수였다면, 2^10 = (2^5) * (2^5)이므로 temp * temp를 해준다.
        if B%2==0:
            return (temp*temp)%C
        # 만약 B가 홀수였다면, 2^11 = 2 * (2^5) * (2^5)이므로 A * temp * temp를 해준다.
        else:
            return (A*temp*temp)%C

print(func(A,B))