GitBook

这里写图片描述

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

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

所以计数时遇见奇数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\n",cnt);
	}
	return 0;
}

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