题目描述

FJ的奶牛想要快速计算整数P的幂 (1 <= P <=20,000),它们需要你的帮助。因为计算极大数的幂,所以它们同一时间仅能使用2个存储器,每个存储器可记录某个结果值。

第一件工作是初始化存储器内的值一个为底数x, 另一个为1。 奶牛可以相乘或相除2个存储器中的值,并把结果存在其中某个存储器内,但所有存储的结果必须是整数。

例如, 如果他们想计算x^31, 一种计算方法是:

WV1 WV2

开始: x 1

存储器1和存储器2相乘,结果存于存储器2: x x^2

存储器2和存储器2相乘,结果存于存储器2: x x^4

存储器2和存储器2相乘,结果存于存储器2: x x^8

存储器2和存储器2相乘,结果存于存储器2: x x^16

存储器2和存储器2相乘,结果存于存储器2: x x^32

存储器2和存储器1相乘,结果存于存储器2: x x^31

因此, x^31可以通过6次计算得出。给出要计算的幂次,要求求出最少需要几次计算。

输入格式

仅一个整数: P。

输出格式

仅一个整数:最少计算次数。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论