Responsive image

问题 1107 --最少乘法次数

1107: 最少乘法次数

时间限制: 10 Sec  内存限制: 128 MB
提交: 41  解决: 23
[提交][状态][讨论版][命题人:]

题目描述

给你一个正整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。 如2^4：2*2=2^2（第一次乘），2^2*2^2=2^4（第二次乘），所以最少共2次。 2^11：2*2=2^2（第一次乘），2^2*2^2=2^4（第二次乘）2^4*2^4=2^8（第三次乘）2^8*2^2=2^10（第四次乘）2^10*2^1=2^11（第五次乘）所以最少共5次。

输入描述

第一行m表示有m(1<=m<=100)组测试数据；每一组测试数据有一整数n（0 < n < 200)

输出描述

输出每组测试数据所需次数s;

样例输入

3
2
3
4

样例输出

1
2
2

提示

2^22,意思是2的22次方

来源

11级曹相召 

[提交][状态]
ACM算法攻关部