2169D1.md (1847B)
1 Source: https://codeforces.com/problemset/problem/2169/D1 2 3 D1. Removal of a Sequence (Easy Version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is the easy version of the problem. The difference between the versions is the constraint on $x$; in this version, $x \le 10^5$. 22 23 Polycarp has a sequence of all natural numbers from $1$ to $10^{12}$. He decides to modify this sequence by performing the following action $x$ times: 24 25 * Simultaneously remove all numbers at positions $y$, $2 \cdot y$, $3 \cdot y$, ..., $m \cdot y \le n$, where $n$ is the length of the current sequence. 26 27 After that, Polycarp wants to find the $k$-th number in the remaining sequence or determine that the length of the resulting sequence is less than $k$. 28 29 Help Polycarp solve this problem! 30 31 Consider an example. Let $x = 2$, $y = 3$, $k = 5$, then: 32 33  34 35 The numbers crossed out with a red line were removed after the first operation, and the numbers crossed out with a blue line were removed after the second operation. Thus, the number at position $k = 5$ is the number $10$. 36 37 Input 38 39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). The description of the test cases follows. 40 41 The only line of each test case contains three integers $x$, $y$, $k$ ($1 \le x \le \bf{10^{5}}$, $1 \le y, k \le 10^{12}$). 42 43 Output 44 45 For each test case, output a positive integer that is at the $k$-th position in the resulting sequence, or $-1$ if the length of the resulting sequence is less than $k$. 46 47 Example 48 49 Input 50 51 ``` 52 6 53 54 2 3 5 55 56 2 5 1 57 58 20 2 1000000000000 59 60 175 10 28 61 62 100000 998244353 1999999999 63 64 1 1 1 65 ``` 66 67 Output 68 69 ``` 70 10 71 72 1 73 74 -1 75 76 2339030304 77 78 2000199999 79 80 -1 81 ```