시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 355 | 102 | 58 | 42.963% |
x의 P승을(1 ≤ P ≤ 20,000) 최대한 빠르게 계산하고자 한다. 그런데 계산결과가 굉장히 크므로 여기서는 계산 도중 값을 저장하는 데 있어 두 개의 변수만을 사용한다.
두 변수 중 하나는 x로, 다른 하나는 1로 초기화되어 있다. 우리가 쓸 수 있는 연산은, 현재 저장되어 있는 값들을 서로 곱하거나 나누어서 그 결과값을 임의의 변수에 저장하는 것이다. 최종 결과가 저장되는 위치는 아무래도 좋다.
예를 들어 x9을 계산하고자 할 때, 다음과 같은 방법이 가능하다.
연산 회수 | 0 | 1 | 2 | 3 | 4 |
변수1 | x | x | x | x5 | x9 |
변수2 | 1 | x2 | x4 | x4 | x4 |
P를 입력받아, xP를 구하기 위한 최소 연산 회수를 구하여라.
첫째 줄에 P가 들어온다.
최소 연산 회수를 출력한다.
31
6