【NYOJ】[1046] 少乘法次数

问题描述

问题分析

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#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】[1046]最少乘法次数