A16732 | $Removal of a Sequence (Easy Version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是该问题的简单版本。两个版本的区别在于 $x$ 的约束；在本版本中，$x \le 10^5$。 Polycarp 有一个从 $1$ 到 $10^{12}$ 的所有自然数组成的序列。他决定通过执行如下操作 $x$ 次来修改该序列： - 每次操作，会同时移除所有位于第 $y$、$2y$、$3y$、……、$my \le n$ 位置上的数，其中 $n$ 是当前序列的长度。 之后，Polycarp 希望找到剩余序列中的第 $k$ 个数，或者判断最终序列的长度是否小于 $k$。 请帮助 Polycarp 解决这个问题！ 举个例子，设 $x = 2$，$y = 3$，$k = 5$，那么： ![](/uploads/acgo/image/35d8a8cc8008461387d8aec14ab4b4c9_d0be574b89b4.png) 用红线划掉的数字是在第一次操作后被移除的，用蓝线划掉的是第二次操作后被移除的。最终，位置 $k = 5$ 上的数字是 $10$。

每组测试数据包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10$）。 每组测试用例占一行，包含三个整数 $x$、$y$、$k$（$1 \le x \le 10^5$，$1 \le y, k \le 10^{12}$）。

对于每组测试用例，输出最终序列中第 $k$ 位的正整数。如果最终序列长度小于 $k$，则输出 $-1$。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出