1982B.md (2347B)
1 Source: https://codeforces.com/problemset/problem/1982/B 2 3 B. Collatz Conjecture 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Recently, the first-year student Maxim learned about the Collatz conjecture, but he didn't pay much attention during the lecture, so he believes that the following process is mentioned in the conjecture: 22 23 There is a variable $x$ and a constant $y$. The following operation is performed $k$ times: 24 25 * increase $x$ by $1$, then 26 * while the number $x$ is divisible by $y$, divide it by $y$. 27 28 Note that both of these actions are performed sequentially within one operation. 29 30 For example, if the number $x = 16$, $y = 3$, and $k = 2$, then after one operation $x$ becomes $17$, and after another operation $x$ becomes $2$, because after adding one, $x = 18$ is divisible by $3$ twice. 31 32 Given the initial values of $x$, $y$, and $k$, Maxim wants to know what is the final value of $x$. 33 34 Input 35 36 Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. Then follows the description of the test cases. 37 38 The only line of each test case contains three integers $x$, $y$, and $k$ ($1 \le x, k \le 10^{9}$, $2 \le y \le 10^{9}$) — the initial variable, constant and the number of operations. 39 40 Output 41 42 For each test case, output a single integer — the number obtained after applying $k$ operations. 43 44 Example 45 46 Input 47 48 ``` 49 13 50 51 1 3 1 52 53 2 3 1 54 55 24 5 5 56 57 16 3 2 58 59 2 2 1 60 61 1337 18 1 62 63 1 2 144133 64 65 12345678 3 10 66 67 998244353 2 998244353 68 69 998244353 123456789 998244352 70 71 998244354 998241111 998244352 72 73 998244355 2 9982443 74 75 1000000000 1000000000 1000000000 76 ``` 77 78 Output 79 80 ``` 81 2 82 1 83 1 84 2 85 3 86 1338 87 1 88 16936 89 1 90 21180097 91 6486 92 1 93 2 94 ``` 95 96 Note 97 98 In the first test case, there is only one operation applied to $x = 1$, resulting in $x$ becoming $2$. 99 100 In the second test case, for $x = 2$, within one operation, one is added to $x$ and it's divided by $y = 3$, resulting in $x$ becoming $1$. 101 102 In the third test case, $x$ changes as follows: 103 104 * After the first operation, $x = 1$, because $24 + 1 = 25$ and $25$ is divisible by $y = 5$ twice within one operation. 105 * After the second operation, $x = 2$. 106 * After the third operation, $x = 3$. 107 * After the fourth operation, $x = 4$. 108 * After the fifth operation, $x = 1$.