문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

Naive하게 B번 곱하면, 시간 복잡도는 O(B)이다. 대신에, A^B 는 A^(B/2)인 것을 이용하면, 시간을 줄일 수 있을 것이다.

Algorithm

A^x를 구하기 위해, A^(x/2)를 구한다.
A^(x/2)를 제곱하여 A^x를 구한다.
x가 홀수라면, A를 한 번 더 곱한다.

Data Structure

• NxN matrix, 초기 A 저장
• NxN matrix, 결과 저장

결과

Other

시간 복잡도는 O(logB)이다.