【NYOJ】[46]最少乘法次数

可以倒推m的n次方的形成过程
因为每次相乘都是两个数相乘
所以应该优先对半

因为n是奇数时不能分为两个一样的
如5可分为2/3
那么应该是先变为2
然后m2*m=m3
之后再进行相乘计算

所以计数时遇见奇数cnt+=2
偶数时cnt++

#include<stdio.h>
#include<math.h>
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        int cnt=0;
        while(n>1) {
            if(n&1)
                cnt+=2;
            else
                cnt++;
            n/=2;
        }
        printf("%d
",cnt);
    }
    return 0;
}

题目地址:【NYOJ】[46]最少乘法次数