의 간단한 해결법은 A를 b번 곱하는 것이다.
하지만, O(n)의 시간으로 풀기 어려울 크기가 b로 주어진다면?
아래의 두가지 방법으로의 접근이 가능하다. 둘 다 O(nlogn)접근이 가능하게 해주는 방법들이다.
1) 분할 정복 이용
def div(a, b):
if b == 0:
return 1
elif b == 1:
return a % C
elif b%2 == 0:
temp = div(a, b//2)
return (temp*temp) % C
else:
return (a* div(a, b-1)) % C
2) 이진수 응용
def calc(a, b):
ans = 1
while b > 0:
if b % 2 == 1:
ans = (ans*a) % C
a = (a*a) % C
b = b//2
return ans