수의 다중 제곱 빠른 계산

$A^{b}$ 의 간단한 해결법은 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