CF1242D Number Discovery

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$ 时使用的参数。

对于每个测试用例，输出一行答案，表示对应数字 $n$ 在序列 $s$ 中的下标。

在第一个样例中，$s = (1, 2, 3, 4, 5, 9, 6, 7, 13, 8, 10, 18, \ldots)$。$10$ 是序列中的第 $11$ 个数，所以答案是 $11$。 在第二个样例中，$s = (1, 2, 3, 4, 5, 15, 6, 7, 8, 9, 10, 40, \ldots)$。 由 ChatGPT 4.1 翻译