거듭제곱 최소 연산
시간 제한2초메모리 제한128 MB
두 변수만 사용해 곱셈이나 나눗셈 연산으로 x와 1에서 시작해 x^P를 만드는 최소 연산 횟수를 구하는 문제입니다.
문제
1 <= P <= 20,000인 P에 대해 x^P를 가능한 한 적은 연산으로 계산하려고 한다. 계산 중에는 두 개의 변수만 사용할 수 있다.
처음에는 한 변수에 x, 다른 변수에 1이 저장되어 있다. 한 번의 연산에서는 현재 두 변수에 저장된 값 중 두 값을 골라 곱하거나, 한 값을 다른 값으로 나눈 결과를 두 변수 중 하나에 저장한다. 같은 변수를 두 번 골라 제곱할 수도 있다. 최종 결과는 어느 변수에 저장되어도 상관없다.
예를 들어 x^9는 다음과 같이 4번의 연산으로 계산할 수 있다.
P가 주어졌을 때, x^P를 계산하는 데 필요한 최소 연산 횟수를 구하라.
입력
첫째 줄에 P가 주어진다.
출력
최소 연산 횟수를 출력한다.