首页 > 代码库 > 最少乘法次数

最少乘法次数

最少乘法次数

时间限制: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

通过列举一些数据可以看出,对于2 4 8 这些2的幂,需要log2 n 次乘法,那么通过这个私信,每次在N中减去最大的2的幂次,就是最少的次数,
注意第一次求小于等于n的二的最大幂次的计算次数要计入,后面用小于这个数的2的幂就不用在计算了(可以使用之前计算结果)。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN  22
#define LLL 1000000000
#define INF 1000000009
#define eps 0.00000001
/*
给你一个整数,求最少乘法多少次获得这个整数的n次方
*/
int main()
{
    int T,n;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        int tmp = floor(log2(n)),ans = 0;
        bool f = false;
        while (n>0)
        {
            int sub = pow(2, tmp);
            if (n >= sub)
                n -= sub;
            else
            {
                tmp--;
                continue;
            }
            if (!f)
            {
                f = true;
                ans += tmp;
            }
            else
                ans += 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

最少乘法次数