POWER - 거듭제곱 계산

https://velog.io/@hyoreal51/Java-%EA%B1%B0%EB%93%AD%EC%A0%9C%EA%B3%B1-%EA%B3%84%EC%82%B0
이 블로그를 참고하면서 풀었다.

문제
두 수를 입력받아 거듭제곱을 리턴해야 합니다.

입력
인자 1: base

int 타입의 자연수 (base >= 2)
인자 2: exponent

int 타입의 정수 (exponent >= 0)
출력
long 타입으로 리턴
실제 계산 결과를 94,906,249로 나눈 나머지를 리턴

주의
Math.pow 사용 불가
시간복잡도 O(logN) 만족

public long power(int base, int exponent) {
	// 1. 94906249 의 수를 매번 반복해서 쓰기 힘들기에 변수에 할당해주었다.
    int dec = 94906249;
    
    // 2. 시간복잡도 O(logN)을 만족해야하니 2로 나눠야한다
    int half = exponent / 2;
    
    // 3. 재귀를 통해 반복해준다
    long rec = power(base, half);
    
    // 4. 2로 나눴으니 곱해준다.(연산마다 94906249의 나머지를 리턴하라했다)
    long pow = (rec * rec) % dec;
    
    // 5. 밑 설명 참조
    if (exponent % 2 == 1) return (base * pow) % dec;
    else return pow;