← 返回题目列表

Codeforces · 1982/B

B. 科拉茨猜想

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

最近一年级学生Maxim了解到了Collatz猜想,但他在听课时并没有太注意,所以他认为猜想中提到了以下过程:

有一个变量 $$$x$$$ 和一个常量 $$$y$$$。以下操作执行 $$$k$$$ 次:

- 将 $$$x$$$ 增加 $$$1$$$,然后
- 当数字 $$$x$$$ 可以被 $$$y$$$ 整除时,将其除以 $$$y$$$。

例如,如果数字 $$$x = 16$$$、$$$y = 3$$$ 和 $$$k = 2$$$,则经过一次操作后 $$$x$$$ 变为 $$$17$$$,经过另一次操作后 $$$x$$$ 变为 $$$2$$$,因为加一后,$$$x = 18$$$ 可以整除$$$3$$$ 两次。

给定 $$$x$$$、$$$y$$$ 和 $$$k$$$ 的初始值,Maxim 想知道 $$$x$$$ 的最终值是多少。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的唯一行包含三个整数 $$$x$$$、$$$y$$$ 和 $$$k$$$ ($$$1 \le x, k \le 10^{9}$$$, $$$2 \le y \le 10^{9}$$$) - 初始变量、常量和操作数。

输出

对于每个测试用例,输出一个整数 - 应用 $$$k$$$ 操作后获得的数字。

示例

输入 #1

13
1 3 1
2 3 1
24 5 5
16 3 2
2 2 1
1337 18 1
1 2 144133
12345678 3 10
998244353 2 998244353
998244353 123456789 998244352
998244354 998241111 998244352
998244355 2 9982443
1000000000 1000000000 1000000000

输出 #1

2
1
1
2
3
1338
1
16936
1
21180097
6486
1
2

注意

在第一个测试用例中,只有一个操作应用于 $$$x = 1$$$,导致 $$$x$$$ 变为 $$$2$$$。

在第二个测试用例中,对于 $$$x = 2$$$,在一次操作中,$$$x$$$ 加一,然后除以 $$$y = 3$$$,导致 $$$x$$$ 变为 $$$1$$$。

在第三个测试用例中,$$$x$$$ 更改如下:

- 第一次运算后,$$$x = 1$$$,因为 $$$24 + 1 = 25$$$ 且 $$$25$$$ 在一次运算中可被 $$$y = 5$$$ 整除两次。
- 第二次操作后,$$$x = 2$$$。
- 第三次操作后,$$$x = 3$$$。
- 第四次操作后,$$$x = 4$$$。
- 第五次操作后,$$$x = 1$$$。