NKOJ 3743 奶牛幂（启发式搜索）

P3743奶牛求幂

问题描述

约翰的奶牛旨在迅速计算出整数范围内的任意次幂(P)，其中P满足1到2万之间的整数值。

在运算过程中, 它们仅能使用两个存储器来完成任务。

这些牛首先会初始化这两个存储器: 一个用来保存底数x, 另一个则初始化为数值1。

在运算过程中, 它们可以选择进行以下运算: A乘以B、A平方、B平方、A除以B、B除以A、A自乘以及B自乘。

例如, 如果它们的目标是计算x的31次幂，则一种可行的方法是:

由此可见, x^{31}可通过六次运算求得. 请告知所需幂次数值, 请求您助算最少需进行多少次运算.

输入格式

一个整数P

输出格式

一个整数，表示最少计算次数

样例输入 1

31

样例输出 1

6

样例输入 2

1023

样例输出 2

11

---

除此之外，在评估过程中需要用对数函数log₂来进行评估。最重要的剪枝方法是使用gcd来进行优化处理；当遇到(u, v)这样的数对时，在检查是否满足