백준 1629번(python)

---

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

def solve(A, B):
    if(B % 2 > 0):
        return solve(A, B - 1) * A
    elif(B == 0):
        return 1
    elif(B == 1):
        return A
    else:
        # 10^11에서 11을 %2 해줄때의 경우는 홀수와 짝수로 나뉘게 된다.
        # 첫 시작부터 % 12를 붙이고 끝까지 계산을 해보면,
        # 왜 result ** 2 % C가 필요한지 알 수 있다.
        result = solve(A, B//2)
        return result ** 2 % C

# 식을 보는 도중, 여기서 왜 또 %C를 해주는지 헷갈릴 수 있는데,
# solve(A, B)는 (10, 11)의 결괏값이고,
# (10, 11) % C는 문제가 원하는 정답이다.
print(solve(A, B) % C)

result ** 2 % C를 찾느라고 시간이 좀 더 걸렸다.
(10^10%12는 10^5^2%12와 같다.)

이 문제는 코드 길이에 비해 정답률이 낮길래 구글에 검색을 좀 해보았는데, 생각보다 풀이가 다양했다.

문제를 풀고 검색을 통해 다른 방법도 접해보길 바란다.