描述

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

               

输入

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

输出

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

样例输入

3
2
3
4

样例输出

1
2
2

 1 #include<cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int T;
 7     scanf("%d",&T);
 8     while(T--)
 9     {
10         int n;
11         scanf("%d",&n);
12         if(n==1)
13         {
14             printf("0\n");
15             continue;
16         }
17         int ans=0;
18         while(n!=1)
19         {
20             if(n&1)
21             {
22                 n-=1;
23                 ans++;
24             }
25             n/=2;
26             ans++;
27         }
28         printf("%d\n",ans);
29     }
30     return 0;
31 }

 

nyoj 46 最少乘法次数

原文：http://www.cnblogs.com/homura/p/4916967.html