最少乘法次数
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
-
给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。如24：2*2=22（第一次乘），22*22=24（第二次乘），所以最少共2次；
- 输入
- 第一行m表示有m(1<=m<=100)组测试数据；
每一组测试数据有一整数n（0<n<=10000）; - 输出
- 输出每组测试数据所需次数s;
- 样例输入
-
3
2
3
4 - 样例输出
-
1
2
2 - 上传者
- 李剑锋
-
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = ; int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int cnt = ;
int num = ;
while(n){
cnt++;
if(n&) num++;
n >>= ;
}
int ans = cnt+num-;
printf("%d\n",ans);
} return ;
}——
蛮有思考性的一道题，cnt ：最高位数-1 表示的是获取最大数需要乘的次数，num：表示有多少个1，num-1就是这几个 1 乘起来的次数。