CF2240A Another Popcount Problem

给定两个整数 $n$ 和 $k$。 你的任务是构造一个长度为 $k$ 的序列 $a$，其中 $a_1, a_2, \ldots, a_k$ 都是非负整数，满足以下条件： - $\sum_{i=1}^{k} a_i \leq n$ - 使得所有元素二进制中 $1$ 的数量之和（即 $\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 \leq t \leq 10^3$）。 接下来的 $t$ 行，每行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^6$），分别表示序列的最大允许和以及序列的长度。

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

- 第一个测试用例中，$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 \leq 6$，总 popcount 为 $2 + 2 = 4$。 由 ChatGPT 5 翻译