Вам даны два целых числа $$$n$$$ и $$$k$$$.
Ваша задача — построить последовательность $$$a$$$, состоящую из $$$k$$$ целых неотрицательных чисел $$$a_1, a_2, \ldots, a_k$$$, такую что:
Вам нужно вывести только максимально возможное значение $$$\sum_{i=1}^{k} \operatorname{popcount}(a_i)$$$.
Здесь $$$\operatorname{popcount}(x)$$$ обозначает количество битов $$$1$$$ в двоичном представлении числа $$$x$$$. Например, $$$\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)$$$.
62 13 16 214142 1372051000000 1001000000 1000000
1241414213221000000
В первом наборе входных данных $$$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$$$, а сумма равна $$$\operatorname{popcount}(3) + \operatorname{popcount}(3) = 2 + 2 = 4$$$.
| Codeforces Round 1105 (Div. 2) |
|---|
| Закончено |
