소스코드

import sys
input = sys.stdin.readline

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

def hyper_exp(base, n, mod_num):
	if n == 0:
		return 1
	
	half = hyper_exp(base, n // 2, mod_num)
	if n % 2 == 0:
		return (half * half) % mod_num
	else:
		return (base * half * half) % mod_num

print(hyper_exp(A,B,C))

풀이

• A,B,C의 값이 모두 20억 이하의 자연수이다보니, 일반적인 연산 과정을 거치면 시간 초과를 걸리겠다고 생각했습니다(특히 0.5초 제한이다보니)
• 그래서 거듭제곱법을 생각했고, 이를 이용해서 모듈러 연산을 중간중간 수행하도록 로직을 작성하자고 생각했습니다.
  • (5^6) % 12 → (5^3 x 5^3) % 12 → ((5 x 5^2) x (5 x 5^2)) % 12 와 같은 과정을 거친다고 생각하시면 됩니다.
  • 모듈러 연산을 검색해보시면 조금 복잡해보이는 수식이 등장하는데요, 사실 곱셈 연산과 관련해서 (a × b) mod c = ((a mod c) × (b mod c)) mod c 를 만족하기 때문에 제 코드에 문제될 것이 없습니다.