문제 출처 : https://www.acmicpc.net/problem/1629

---

문제 파악

(A^B) % C 를 분할정복을 이용하여 빠르게 계산해야 하는 문제.

예제 입력 1을 보자.

10^11 % 12 → 정석대로 10^11 을 계산하면 너무 크다.
하지만 10^11 은 다음처럼 쪼갤 수 있다.

10^11
= (10^2 × 10^2 × 10^2 × 10^2 × 10^2 × 10^1)

10^2 = 100 → 100 % 12 = 4
10 % 12 = 10

즉 10^11 % 12
= 4^5 × 10
= 10240
10240 % 12 = 4

즉, 큰 지수를 쪼개서 계산하고, 중간 중간 나머지를 취하면 값은 유지하면서 숫자는 작게 관리할 수 있다.

---

이 논리를 수학적으로 멋지게 표현하면

A^B % C
= (A % C × A % C × A % C × … B번 반복 …) % C

---

• 지수가 짝수일 때

A^B = (A^(B/2))^2

• 지수가 홀수일 때

A^B = (A^(⌊B/2⌋))^2 × A

즉, 앞으로 해야 할 일은
큰 B(예: 11)를 매번 반띵(→ 5 → 2 → 1 → 0)하면서 내려가는 것이다.

중간에 등장하는 모든 값은 곱셈의 나머지 성질에 의해 계속 % C 를 취해도 결과값은 변하지 않는다.

---

해답 및 풀이

import sys
input = sys.stdin.readline

# A, B, C 입력
A, B, C = map(int, input().split())

# 분할 정복 함수 정의
def power(a, b):
    # base case: b가 1이면 a % C 리턴
    if b == 1:
        return a % C
    
    # b를 반으로 나눈 값을 재귀 호출
    half = power(a, b // 2)

    # b가 짝수면 half * half
    if b % 2 == 0:
        return (half * half) % C
    # b가 홀수면 half * half * a
    else:
        return (half * half * a) % C

print(power(A, B))