1872 - 最少乘法次数
给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。如24：2*2=22（第一次乘），22*22=24（第二次乘），所以最少共2次；
题目输入
第一行m表示有m(1<=m<=100)组测试数据；
每一组测试数据有一整数n（0<n<=10000）;
题目输出
输出每组测试数据所需次数s;
输入/输出样例
题目输入
4 2 3 4 1000
题目输出
1 2 2 14
提示
这是一种快速乘方算法的思想，由此可以看出，原始乘方算法可以被极大的优化。
C语言解答
#include <stdio.h> int count(int n){ int cnt = n%2?1:0; if(n>2) return count(n/2) + cnt + 1; if(n==2) return 1; return 0; } int main(){ int m; scanf("%d", &m); while(m--){ int n, i, cnt = 0; scanf("%d", &n); printf("%d\n", count(n)); } return 0; }
C++解答
#include <cstdio> int t,n,s; int main() { scanf("%d",&t); while(t--) { s=0; scanf("%d",&n); while(n!=1) { if(n&1) s++; n=n>>1; s++; } printf("%d\n",s); } return 0; }
提示
这是一种快速乘方算法的思想，由此可以看出，原始乘方算法可以被极大的优化。