← 返回题目列表

Codeforces · 2169/D2

D2. 删除序列(硬版本)

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

这是问题的困难版本。版本之间的区别在于 $$$x$$$ 的约束;在此版本中,$$$x \le 10^{12}$$$。

Polycarp 具有从 $$$1$$$ 到 $$$10^{12}$$$ 的所有自然数序列。他决定通过执行以下操作 $$$x$$$ 次来修改此序列:

  • 同时删除 $$$y$$$、$$$2 \cdot y$$$、$$$3 \cdot y$$$、...、$$$m \cdot y \le n$$$ 位置处的所有数字,其中 $$$n$$$ 是当前序列的长度。

之后,Polycarp 想要找到剩余序列中的第 $$$k$$$ 个数字,或者确定结果序列的长度小于 $$$k$$$。

帮助Polycarp解决这个问题!

考虑一个例子。设 $$$x = 2$$$, $$$y = 3$$$, $$$k = 5$$$,则:

第一次操作后,红线划掉的数字被删除,第二次操作后,蓝线划掉的数字被删除。因此,位置 $$$k = 5$$$ 处的数字是数字 $$$10$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。测试用例的描述如下。

每个测试用例的唯一行包含三个整数 $$$x$$$、$$$y$$$、$$$k$$$ ($$$1 \le x, y, k \le 10^{12}$$$)。

输出

对于每个测试用例,输出结果序列中第 $$$k$$$ 位置的正整数,或者如果结果序列的长度小于 $$$k$$$,则输出 $$$-1$$$。

示例

输入
复制

6
2 3 5
2 5 1
20 2 1000000000000
175 10 28
1000000000 998244353 1999999999
1 1 1

输出
复制

10
1
-1
2339030304
4672518823
-1