빠른 거듭제곱

시간 제한: 1000 ms메모리 제한: 256 MBSilver V

3

작성자: 관리자

문제

$a^n$ 은 $a^{n-1} \times a$ 이므로 $n$ 을 1씩 줄이는 재귀로 구할 수 있지만, 그러면 함수를 $n + 1$ 번 호출한다. $n$ 이 짝수이면 $a^n = a^{n/2} \times a^{n/2}$ 이고, 홀수이면 $a^n = a^{n/2} \times a^{n/2} \times a$ 이다(n / 2는 정수 나눗셈). $n$ 을 절반씩 줄이면 호출 횟수가 $\log_2 n$ 정도로 줄어든다.

정수 $a$ 와 $n$ 을 입력받아 $a^n$ 을 출력한다. $a^{n/2}$ 는 한 번만 호출해 변수에 저장한다.

입력

첫째 줄에 정수 $a$ 와 $n$ 이 공백 하나를 사이에 두고 주어진다.

출력

첫째 줄에 $a^n$ 을 출력한다.

제한

$1 \le a \le 1\,000\,000\,000$
$0 \le n \le 1\,000\,000\,000$

문제 통계

1

전체 제출

1

정답

100%

정답률

1

정답자 수

000

a^n \le 10^{18}

$n$ 을 1씩 줄이는 재귀는 $a = 1$ , $n = 1\,000\,000\,000$ 에서 호출이 너무 깊어져 실행 중에 비정상 종료한다.

입출력 예시

입력 1

3 13

출력 1

입력 2

2 10

출력 2