ZLSOJ

问题 N: 最少乘法次数

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

给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。如2⁴：2*2=2²（第一次乘），2²*2²=2⁴（第二次乘），所以最少共2次；

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

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

这是一种快速乘方算法的思想，由此可以看出，原始乘方算法可以被极大的优化。