← 返回题目列表

Codeforces · 1242/D

D. 号码发现

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

Ujan 需要在清理工作中休息一下,所以他开始玩无限序列。他有两个整数 $$$n$$$ 和 $$$k$$$。他通过重复以下步骤创建了一个无限序列$$$s$$$。

1. 查找 $$$k$$$ 不在 $$$s$$$ 中的最小不同正整数。我们从最小到最大将它们称为 $$$u_{1}, u_{2}, \ldots, u_{k}$$$。
2. 按顺序将 $$$u_{1}、u_{2}、\ldots、u_{k}$$$ 和 $$$\sum_{i=1}^{k} u_{i}$$$ 附加到 $$$s$$$。
3. 返回第一步。

当 Ujan 在 $$$s$$$ 序列中写下数字 $$$n$$$ 时,他将停止拖延。帮助他找到$$$n$$$在$$$s$$$中的索引。换句话说,找到整数 $$$x$$$ 使得 $$$s_{x} = n$$$。可以证明所有正整数都只包含在 $$$s$$$ 中一次。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{5}$$$),测试用例的数量。

以下 $$$t$$$ 行中的每一行都包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le k \le 10^{6}$$$)、要在序列 $$$s$$$ 中找到的数字以及用于创建序列 $$$s$$$ 的参数。

输出

在每一 $$$t$$$ 行中,输出相应测试用例的答案。

示例

输入 #1

2
10 2
40 5

输出 #1

11
12

注意

在第一个示例中,$$$s = (1, 2, 3, 4, 5, 9, 6, 7, 13, 8, 10, 18, \dots)$$$。 $$$10$$$ 是这里的第 $$$11$$$ 个数字,所以答案是 $$$11$$$。

在第二个示例中,$$$s = (1, 2, 3, 4, 5, 15, 6, 7, 8, 9, 10, 40, \dots)$$$。