/ MYOJ / 题库 /

[b6e0OJ]倍数

[b6e0OJ]倍数

测试数据来自 b6e0_OJ/1015

题目描述

给定一个正整数\(n\),对于\(n\)的所有倍数(不为\(0\)),其二进制表示下\(1\)的个数的最小值是多少?
例如\(5\)的二进制表示为\(101\),其中\(1\)的个数为\(2\)。

输入格式

共\(T\)行,第\(i\)行一个正整数,表示第\(i\)个询问的答案。

输出格式

输出到达第\(n\)阶花费的最少体力。

输入输出样例

输入

3
2
4
11

输出

1
1
2

样例解释

\(2\)的倍数:\(2\)二进制表示为\(10\),\(1\)的个数为\(1\)个。
\(4\)的倍数:\(4\)二进制表示为\(100\),\(1\)的个数为\(1\)个。
\(11\)的倍数:\(33\)二进制表示为\(100001\),\(1\)的个数为\(2\)个。

数据范围

对于100%的数据,\(1\le n\le4\times10^6\),\(1\le T\le3\)。
Subtask 1(30pts):\(1\le n\le20\)。
Subtask 2(20pts):\(1\le n\le1000\)。
Subtask 3(30pts):\(1\le n\le10^5\)。
Subtask 4(20pts):无特殊限制。

贡献者

题面,数据: 关怀大佬
核题: Ducati,b6e0

信息

ID
1047
难度
9
分类
(无)
标签
递交数
2
已通过
1
通过率
50%
上传者