소스코드
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))
Python
복사
풀이
•
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 를 만족하기 때문에 제 코드에 문제될 것이 없습니다.