← 返回题目列表

Codeforces · 1988/A

A. 拆分多重集

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

多重集是一组数字,其中可以有相同的元素,并且数字的顺序并不重要。例如,$$$\{2,2,4\}$$$ 是多重集。

您有一个多重集$$$S$$$。最初,多重集仅包含一个正整数$$$n$$$。即$$$S=\{n\}$$$。此外,还有一个给定的正整数$$$k$$$。

在一次操作中,您可以选择 $$$S$$$ 中的任意正整数 $$$u$$$ 并从 $$$S$$$ 中删除 $$$u$$$ 的一份副本。然后,向$$$S$$$中插入不超过$$$k$$$个正整数,使得所有插入的整数之和等于$$$u$$$。

求使 $$$S$$$ 包含 $$$n$$$ 的最少操作数。

输入

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

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

输出

对于每个测试用例,打印一个整数,这是所需的答案。

示例

输入 #1

4
1 5
5 2
6 3
16 4

输出 #1

0
4
3
5

注意

对于第一个测试用例,最初$$$S=\{1\}$$$,已经满足要求。因此,我们需要零操作。

对于第二个测试用例,最初为 $$$S=\{5\}$$$。我们可以应用以下操作:

- 选择$$$u=5$$$,从$$$S$$$中删除$$$u$$$,并将$$$2,3$$$插入$$$S$$$中。现在,$$$S=\{2,3\}$$$。
- 选择$$$u=2$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,3\}$$$。
- 选择$$$u=3$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,2$$$插入$$$S$$$中。现在,$$$S=\{1,1,1,2\}$$$。
- 选择$$$u=2$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,1,1,1\}$$$。

总共使用 $$$4$$$ 操作,我们实现了目标。

对于第三个测试用例,最初为 $$$S=\{6\}$$$。我们可以应用以下操作:

- 选择$$$u=6$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,2,3$$$插入$$$S$$$。现在,$$$S=\{1,2,3\}$$$。
- 选择$$$u=2$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,1,3\}$$$。
- 选择$$$u=3$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,1,1,1,1\}$$$。

总共使用 $$$3$$$ 操作,我们实现了目标。

对于第四个测试用例,最初为 $$$S=\{16\}$$$。我们可以应用以下操作:

- 选择$$$u=16$$$,从$$$S$$$中删除$$$u$$$,并将$$$4,4,4,4$$$插入$$$S$$$。现在,$$$S=\{4,4,4,4\}$$$。
- 重复$$$4$$$次:选择$$$u=4$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1,1,1$$$插入$$$S$$$。

总共使用 $$$5$$$ 操作,我们实现了目标。