← 返回题目列表

Codeforces · 2053/C

C. 迷人的观星者

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

艾丽丝看着星星,脑海中浮现出一个美丽的问题。她邀请你解决这个问题,以便相信流星雨的形成。

天空中有 $$$n$$$ 颗星星,排列成一排。艾里斯有一架望远镜,她用它来观察星星。

最初,Iris 观察了 $$$[1, n]$$$ 段中的星星,她的幸运值为 $$$0$$$。 Iris 想要为她观察到的每个段 $$$[l, r]$$$ 寻找中间位置的星星。因此使用以下递归过程:

- 首先,她将计算 $$$m = \left\lfloor \frac{l+r}{2} \right\rfloor$$$。
- 如果该段的长度(即 $$$r - l + 1$$$)是偶数,Iris 会将其分为两个等长的段 $$$[l, m]$$$ 和 $$$[m+1, r]$$$ 以便进一步观察。
- 否则,Iris会将望远镜瞄准恒星$$$m$$$,她的幸运值将增加$$$m$$$;随后,如果 $$$l \neq r$$$,Iris 将继续观察两个段 $$$[l, m-1]$$$ 和 $$$[m+1, r]$$$。

Iris 有点懒。她用整数 $$$k$$$ 定义自己的懒惰:随着观察的进行,她将不会继续观察长度严格小于 $$$k$$$ 的任何段 $$$[l, r]$$$。在这种情况下,请预测她最终的幸运值。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot 10^9$$$)。

输出

对于每个测试用例,输出一个整数——最终的幸运值。

示例

输入 #1

6
7 2
11 3
55 13
5801 6
8919 64
8765432 1

输出 #1

12
18
196
1975581
958900
38416403456028

注意

在第一个测试用例中,一开始,Iris 观察到 $$$[1, 7]$$$。由于 $$$[1, 7]$$$ 的长度为奇数,她的目标是星星 $$$4$$$,因此她的幸运值增加了 $$$4$$$。然后它被分成 $$$2$$$ 新段:$$$[1, 3]$$$ 和 $$$[5, 7]$$$。 $$$[1, 3]$$$ 段的长度再次为奇数,因此 Iris 瞄准星星 $$$2$$$ 并将她的幸运值增加 $$$2$$$。然后将其分割成$$$2$$$新段:$$$[1, 1]$$$和$$$[3, 3]$$$,两者的长度均小于$$$2$$$,因此不再进行进一步观察。对于范围 $$$[5, 7]$$$,进度类似,幸运值最终增加 $$$6$$$。因此,最终的幸运值为$$$4 + 2 + 6 = 12$$$。

在最后一个测试用例中,Iris 最终观察到了所有星星,最终的幸运值是 $$$1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028$$$。