Problem I: 马小云的快速幂

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $78$ 正确数量 $20$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

传统的计算a^n=a*a*....a一般需要计算n-1次乘法

快速幂采用二分算法可以把算法大大加速:算法思想如下:

f(a,n){

if(n==0)return 1;

if(n==1)return a;

t=f(a,n/2);//二分法

if(n%2==0)return t*t;

else return t*t*a;

}

你的任务是计算按照这个算法计算a^n要执行的乘法次数

多组输入,每组一个非负整数代表 n <=2^62


输出二分算法执行的乘法次数
1
2
4
0
1
2