← 返回题目列表

Codeforces · 2020/A

A. 求最少运算

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

给你两个整数 $$$n$$$ 和 $$$k$$$。

在一次运算中,您可以从 $$$n$$$ 中减去 $$$k$$$ 的任意幂。形式上,在一次操作中,对于任何非负整数 $$$x$$$,您可以将 $$$n$$$ 替换为 $$$(n-k^x)$$$。

求使 $$$n$$$ 等于 $$$0$$$ 所需的最少操作数。

输入

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

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^9$$$)。

输出

对于每个测试用例,在新行中输出最小操作数。

示例

输入 #1

6
5 2
3 5
16 4
100 3
6492 10
10 1

输出 #1

2
3
1
4
21
10

注意

在第一个测试用例中,$$$n = 5$$$ 和 $$$k = 2$$$。我们可以执行以下操作序列:

1. 从 $$$5$$$ 中减去 $$$2^0 = 1$$$。 $$$n$$$ 的当前值变为 $$$5 - 1 = 4$$$。
2. 从 $$$4$$$ 中减去 $$$2^2 = 4$$$。 $$$n$$$ 的当前值变为 $$$4 - 4 = 0$$$。

可以证明,在小于 $$$2$$$ 的操作中,无法使 $$$n$$$ 等于 $$$0$$$。因此,$$$2$$$ 就是答案。

在第二个测试用例中,$$$n = 3$$$ 和 $$$k = 5$$$。我们可以执行以下操作序列:

1. 从 $$$3$$$ 中减去 $$$5^0 = 1$$$。 $$$n$$$ 的当前值变为 $$$3 - 1 = 2$$$。
2. 从 $$$2$$$ 中减去 $$$5^0 = 1$$$。 $$$n$$$ 的当前值变为 $$$2 - 1 = 1$$$。
3. 从 $$$1$$$ 中减去 $$$5^0 = 1$$$。 $$$n$$$ 的当前值变为 $$$1 - 1 = 0$$$。

可以证明,在小于 $$$3$$$ 的操作中,无法使 $$$n$$$ 等于 $$$0$$$。因此,$$$3$$$ 就是答案。