CF1759F All Possible Digits

在黑板上写有一个长度为 $n$ 的 $p$ 进制正整数 $x$（$2 \le p \le 10^9$）。该数 $x$ 以序列 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）的形式给出，表示 $x$ 的各位数字，从高位到低位依次排列（最高位到最低位）。 Dmitry 非常喜欢这个进制的所有数字，他希望每个数字至少在黑板上出现一次。 每次操作，他可以： - 任选一个写在黑板上的数 $x$，将其加 $1$，并把新值 $x+1$ 写在黑板上。 例如，$p=5$，$x=234_5$。 - 初始时，黑板上有数字 $2$、$3$ 和 $4$； - Dmitry 将 $234_5$ 加 $1$，得到 $240_5$，此时黑板上有数字 $0$、$2$、$3$、$4$； - Dmitry 再将 $240_5$ 加 $1$，得到 $241_5$，此时黑板上有 $0$ 到 $4$ 的所有数字。 你的任务是求出，最少需要多少次操作，才能使黑板上出现 $0$ 到 $p-1$ 的所有数字，每个数字至少出现一次。

输入的第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$（$1 \le n \le 100$）和 $p$（$2 \le p \le 10^9$），分别表示数字的长度和进制。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$），表示 $p$ 进制下 $x$ 的各位数字。 保证 $x$ 没有前导零（即 $a_1 > 0$）。

对于每个测试用例，输出一个整数，表示 Dmitry 至少需要多少次操作，才能使黑板上出现 $0$ 到 $p-1$ 的所有数字。 可以证明，总是存在有限次操作可以实现目标。

由 ChatGPT 4.1 翻译