奶牛计算整数幂

题目描述

约翰的奶牛希望能够非常快速地计算一个数字的整数幂 $P$ 是多少。

在它们计算得到最终结果的过程中只能保留两个工作变量用于中间结果。

初始状态

• 第一个工作变量初始化为 $x$
• 第二个工作变量初始化为 $1$

操作规则

奶牛可以将任意一对工作变量相乘或相除（可以是一个工作变量与自己相乘或相除），并将结果储存在任意一个工作变量中，但是所有结果都只能储存为整数。

目标

给定希望求得的具体次幂数 $P$，计算至少需要多少个操作才能得到 $x^P$。

输入格式

输入包含一个整数 $P$，表示具体次幂数。

输出格式

输出包含一个整数，表示所需最少操作数。

数据范围

$1 \le P \le 20000$

输入样例

31

输出样例

6

样例解释

奶牛需要计算 $x^{31}$。

一种最优执行方法如下：

因此，$x^{31}$ 经过 6 个操作就可得到。

操作限制

1. 只有两个工作变量：在整个计算过程中，只能使用两个变量存储中间结果
2. 允许的操作：
   • 乘法：变量A × 变量B → 变量C（C可以是A或B）
   • 除法：变量A ÷ 变量B → 变量C（C可以是A或B）
3. 整数结果：所有操作的结果必须是整数
4. 最终目标：使其中一个工作变量的值为 $x^P$

问题本质

这是一个加法链问题的变种：

• 普通加法链：通过加法从1开始构造目标数P，每次可以相加两个已有的数
• 本题变种：通过乘法和除法从集合$\{x, 1\}$开始构造$x^P$，每次可以相乘或相除两个已有的幂

其他示例

对于 $P = 15$，最少操作数：

1. 初始：$(x, 1)$
2. $x × x → x^2$：$(x, x^2)$
3. $x^2 × x → x^3$：$(x, x^3)$
4. $x^3 × x^3 → x^6$：$(x, x^6)$
5. $x^6 × x^6 → x^{12}$：$(x, x^{12})$
6. $x^{12} ÷ x → x^{11}$：$(x, x^{11})$
7. $x^{11} × x^3 → x^{14}$：$(x, x^{14})$
8. $x^{14} × x → x^{15}$：$(x, x^{15})$

需要 8 步操作。

时空限制

• 时间限制：1秒
• 空间限制：64MB