CF1988A Split the Multiset

题目描述

多重集是一个可以包含相等元素的数集，且元素的顺序无关紧要。例如，$\{2,2,4\}$ 是一个多重集。

你有一个多重集 $S$。最初，多重集只包含一个正整数 $n$，即 $S=\{n\}$。另外，给定一个正整数 $k$。

每次操作，你可以选择 $S$ 中的任意一个正整数 $u$，将 $u$ 的一个副本从 $S$ 中移除。然后，向 $S$ 中插入不超过 $k$ 个正整数，使得所有插入的整数之和等于 $u$。

请你求出最少需要多少次操作，才能使 $S$ 中包含 $n$ 个 $1$。

输入格式

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 1000$）。接下来每组测试数据占一行，每行包含两个整数 $n,k$（$1\le n\le 1000,\,2\le k\le 1000$）。

输出格式

对于每组测试数据，输出一个整数，表示所需的最小操作次数。

输入输出样例 #1

输入 #1

4
1 5
5 2
6 3
16 4

输出 #1

0
4
3
5

说明/提示

对于第一个测试用例，初始时 $S=\{1\}$，已经满足要求，因此需要 $0$ 次操作。

对于第二个测试用例，初始时 $S=\{5\}$。可以按如下方式操作：

• 选择 $u=5$，将 $u$ 从 $S$ 中移除，插入 $2,3$ 到 $S$。此时 $S=\{2,3\}$。
• 选择 $u=2$，将 $u$ 从 $S$ 中移除，插入 $1,1$ 到 $S$。此时 $S=\{1,1,3\}$。
• 选择 $u=3$，将 $u$ 从 $S$ 中移除，插入 $1,2$ 到 $S$。此时 $S=\{1,1,1,2\}$。
• 选择 $u=2$，将 $u$ 从 $S$ 中移除，插入 $1,1$ 到 $S$。此时 $S=\{1,1,1,1,1\}$。

共进行了 $4$ 次操作，达成目标。

对于第三个测试用例，初始时 $S=\{6\}$。可以按如下方式操作：

• 选择 $u=6$，将 $u$ 从 $S$ 中移除，插入 $1,2,3$ 到 $S$。此时 $S=\{1,2,3\}$。
• 选择 $u=2$，将 $u$ 从 $S$ 中移除，插入 $1,1$ 到 $S$。此时 $S=\{1,1,1,3\}$。
• 选择 $u=3$，将 $u$ 从 $S$ 中移除，插入 $1,1,1$ 到 $S$。此时 $S=\{1,1,1,1,1,1\}$。

共进行了 $3$ 次操作，达成目标。

对于第四个测试用例，初始时 $S=\{16\}$。可以按如下方式操作：

• 选择 $u=16$，将 $u$ 从 $S$ 中移除，插入 $4,4,4,4$ 到 $S$。此时 $S=\{4,4,4,4\}$。
• 重复 $4$ 次：选择 $u=4$，将 $u$ 从 $S$ 中移除，插入 $1,1,1,1$ 到 $S$。

共进行了 $5$ 次操作，达成目标。

由 ChatGPT 4.1 翻译