← 返回题目列表

Codeforces · 2240/A

A. 另一个 Popcount 问题

中文机器翻译题面 查看原题

给你两个整数 $$$n$$$ 和 $$$k$$$。

你的任务是构造一个由 $$$k$$$ 非负整数 $$$a_1, a_2, \ldots, a_k$$$ 组成的序列 $$$a$$$ ,使得:

  • $$$\sum_{i=1}^{k} a_i \le n$$$
  • 设置位的总数,即 $$$\sum_{i=1}^{k} \operatorname{popcount}(a_i)$$$ 尽可能大。

你只需要输出 $$$\sum_{i=1}^{k} \operatorname{popcount}(a_i)$$$ 的最大可能值。

这里,$$$\operatorname{popcount}(x)$$$ 表示$$$x$$$ 的二进制表示中$$$1$$$ 的位数。例如,$$$\operatorname{popcount}(6) = \operatorname{popcount}((110)_2) = 2$$$,$$$\operatorname{popcount}(0) = 0$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

接下来的 $$$t$$$ 行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^6$$$) — 分别是序列的最大允许总和和序列的长度。

输出

对于每个测试用例,输出一个整数 - $$$\sum_{i=1}^{k} \operatorname{popcount}(a_i)$$$ 的最大可能值。

示例

输入
复制

6
2 1
3 1
6 2
14142 137205
1000000 100
1000000 1000000

输出
复制

1
2
4
14142
1322
1000000

注意

在第一个测试用例中,$$$n=2$$$ 和 $$$k=1$$$。我们可以选择 $$$a = [1]$$$ 或 $$$a = [2]$$$。在这两种情况下,popcount 的总和都是 $$$1$$$。

在第二个测试用例中,$$$n=3$$$ 和 $$$k=1$$$。我们可以选择$$$a = [3]$$$,因为$$$(3)_2 = (11)_2$$$,$$$\operatorname{popcount}(3) = 2$$$。

在第三个测试用例中,$$$n=6$$$ 和 $$$k=2$$$。我们可以选择 $$$a = [3, 3]$$$。总和为 $$$3 + 3 = 6 \le 6$$$,总 popcount 为 $$$\operatorname{popcount}(3) + \operatorname{popcount}(3) = 2 + 2 = 4$$$。