악곱 == 악성곱슬

분할 정복

---

이 문제는 분할 정복 기법을 이용해 거듭 제곱을 구하는 문제이다. 입력이 무려 21억씩이다.

import sys

def divide(a, b, c):
    if b == 1:
        return a % c
    tmp = divide(a, b // 2, c)
    if b % 2 == 0:
        return tmp * tmp % c
    else:
        return tmp * tmp * a % c

if __name__ == "__main__":
    A, B, C = map(int, sys.stdin.readline().rstrip().split())
    print(divide(A, B, C))