YOKOF - Power Calculus
题意翻译
(略过没有营养的题干)
**题目大意**:
给出正整数n,若只能使用乘法或除法,输出使x经过运算(自己乘或除自己,以及乘或除运算过程中产生的中间结果)变成x^n的最少步数
***输入格式***:
若干行数据,每行一个正整数n,数据以单独成行的0结束
***输出格式***:
若干行数据,对应每行输入的n所需的步数
题目描述
Starting with _x_ and repeatedly multiplying by _x_, we can compute _x_ $ ^{31} $ with thirty multiplications:
> _x_ $ ^{2} $ = _x_ \* _x_, _x_ $ ^{3} $ = _x_ $ ^{2} $ \* _x_, _x_ $ ^{4} $ = _x_ $ ^{3} $ \* _x_, ... , _x_ $ ^{31} $ = _x_ $ ^{30} $ \* _x_.
The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute _x_ $ ^{31} $ with eight multiplications:
> _x_ $ ^{2} $ = _x_ \* _x_, _x_ $ ^{3} $ = _x_ $ ^{2} $ \* _x_, _x_ $ ^{6} $ = _x_ $ ^{3} $ \* _x_ $ ^{3} $ , _x_ $ ^{7} $ = _x_ $ ^{6} $ \* _x_, _x_ $ ^{14} $ = _x_ $ ^{7} $ \* _x_ $ ^{7} $ ,
> _x_ $ ^{15} $ = _x_ $ ^{14} $ \* _x_, _x_ $ ^{30} $ = _x_ $ ^{15} $ \* _x_ $ ^{15} $ , _x_ $ ^{31} $ = _x_ $ ^{30} $ \* _x_.
This is not the shortest sequence of multiplications to compute _x_ $ ^{31} $ . There are many ways with only seven multiplications. The following is one of them:
> _x_ $ ^{2} $ = _x_ \* _x_, _x_ $ ^{4} $ = _x_ $ ^{2} $ \* _x_ $ ^{2} $ , _x_ $ ^{8} $ = _x_ $ ^{4} $ \* _x_ $ ^{4} $ , _x_ $ ^{10} $ = _x_ $ ^{8} $ \* _x_ $ ^{2} $ ,
> _x_ $ ^{20} $ = _x_ $ ^{10} $ \* _x_ $ ^{10} $ , _x_ $ ^{30} $ = _x_ $ ^{20} $ \* _x_ $ ^{10} $ , _x_ $ ^{31} $ = _x_ $ ^{30} $ \* _x_.
There however is no way to compute _x_ $ ^{31} $ with fewer multiplications. Thus this is one of the most efficient ways to compute _x_ $ ^{31} $ only by multiplications.
If division is also available, we can find a shorter sequence of operations. It is possible to compute _x_ $ ^{31} $ with six operations (five multiplications and one division):
> _x_ $ ^{2} $ = _x_ \* _x_, _x_ $ ^{4} $ = _x_ $ ^{2} $ \* _x_ $ ^{2} $ , _x_ $ ^{8} $ = _x_ $ ^{4} $ \* _x_ $ ^{4} $ , _x_ $ ^{16} $ = _x_ $ ^{8} $ \* _x_ $ ^{8} $ , _x_ $ ^{32} $ = _x_ $ ^{16} $ \* _x_ $ ^{16} $ , _x_ $ ^{31} $ = _x_ $ ^{32} $ ÷ _x_.
This is one of the most efficient ways to compute _x_ $ ^{31} $ if a division is as fast as a multiplication.
Your mission is to write a program to find the least number of operations to compute _x_ $ ^{n} $ by multiplication and division starting with _x_ for the given positive integer _n_. Products and quotients appearing in the sequence of operations should be _x_ to a positive integer's power. In other words, _x_ $ ^{-3} $ , for example, should never appear.
输入输出格式
输入格式
The input is a sequence of one or more lines each containing a single integer _n_. _n_ is positive and less than or equal to 1000. The end of the input is indicated by a zero.
输出格式
Your program should print the least total number of multiplications and divisions required to compute _x_ $ ^{n} $ starting with _x_ for the integer _n_. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.
输入输出样例
输入样例 #1
1
31
70
91
473
512
811
953
0
输出样例 #1
0
6
8
9
11
9
13
12