CF1909D.Split Plus K

eliteLAQ - Desert Ruins

⠀

There are $n$ positive integers $a_1, a_2, \dots, a_n$ on a blackboard. You are also given a positive integer $k$. You can perform the following operation some (possibly $0$) times:

• choose a number $x$ on the blackboard;
• erase one occurrence of $x$;
• write two positive integers $y$, $z$ such that $y+z = x+k$ on the blackboard.

Is it possible to make all the numbers on the blackboard equal? If yes, what is the minimum number of operations you need?

eliteLAQ - 沙漠遗迹

⠀

黑板上有 $n$ 个正整数 $a_1, a_2, \dots, a_n$。同时给定一个正整数 $k$。你可以执行以下操作若干次（可以为 $0$ 次）：

• 选择黑板上的一个数 $x$；
• 擦除该数 $x$ 的一次出现；
• 在黑板上写下两个正整数 $y$、$z$，满足 $y+z = x+k$。

是否可能使黑板上所有数字都相等？如果可以，最少需要多少次操作？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \leq k \leq 10^{12}$) — the number of integers initially on the blackboard and the constant $k$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{12}$) — the initial state of the blackboard.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$、$k$（$1 \le n \le 2 \cdot 10^5$，$1 \leq k \leq 10^{12}$）——分别表示黑板上初始的整数个数和常数 $k$。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{12}$）——表示黑板的初始状态。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single line containing an integer: the minimum number of operations you need to make all the numbers on the blackboard equal, or $-1$ if it is impossible.

对于每个测试用例，输出一行包含一个整数：使黑板上所有数字相等所需的最少操作次数；如果不可能实现，则输出 $-1$。

In the first test case, $k = 1$. You can make all the numbers on the blackboard equal to $2$ with the following operations:

• Erase $x = 4$ and write $(y, z) = (2, 3)$. Note that $y+z=x+k$. The blackboard now contains the multiset ${3, 2, 3}$.
• Erase $x = 3$ and write $(y, z) = (2, 2)$. Note that $y+z=x+k$. The blackboard now contains ${2, 2, 2, 3}$.
• Erase $x = 3$ and write $(y, z) = (2, 2)$. Note that $y+z=x+k$. The blackboard now contains ${2, 2, 2, 2, 2}$.

This makes all the numbers equal in $3$ operations. It can be shown that you cannot make all the numbers equal in less than $3$ operations.

In the second test case, $k = 3$. You can make all the numbers on the blackboard equal to $7$ with the following operation:

• Erase $x = 11$ and write $(y, z) = (7, 7)$. Note that $y+z=x+k$. The blackboard now contains ${7, 7, 7}$.

In the third test case, $k = 10$. You can make all the numbers on the blackboard equal to $40$ with the following operations:

• Erase $x = 100$ and write $(y, z) = (70, 40)$. Note that $y+z=x+k$. The blackboard now contains ${70, 40, 40, 100}$.
• Erase $x = 70$ and write $(y, z) = (40, 40)$. Note that $y+z=x+k$. The blackboard now contains ${40, 40, 40, 40, 100}$.
• Erase $x = 100$ and write $(y, z) = (40, 70)$. Note that $y+z=x+k$. The blackboard now contains ${40, 40, 40, 40, 40, 70}$.
• Erase $x = 70$ and write $(y, z) = (40, 40)$. Note that $y+z=x+k$. The blackboard now contains ${40, 40, 40, 40, 40, 40, 40}$.

In the fourth and in the fifth test case, you can show that it is impossible to make all the numbers on the blackboard equal.

在第一个测试用例中，$k = 1$。你可以通过以下操作使黑板上的所有数字都变为 $2$：

• 擦除 $x = 4$，写入 $(y, z) = (2, 3)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{3, 2, 3\}$。
• 擦除 $x = 3$，写入 $(y, z) = (2, 2)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{2, 2, 2, 3\}$。
• 擦除 $x = 3$，写入 $(y, z) = (2, 2)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{2, 2, 2, 2, 2\}$。

这共需 $3$ 次操作使得所有数字相等。可以证明，无法用少于 $3$ 次操作使所有数字相等。

在第二个测试用例中，$k = 3$。你可以通过以下操作使黑板上的所有数字都变为 $7$：

• 擦除 $x = 11$，写入 $(y, z) = (7, 7)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{7, 7, 7\}$。

在第三个测试用例中，$k = 10$。你可以通过以下操作使黑板上的所有数字都变为 $40$：

• 擦除 $x = 100$，写入 $(y, z) = (70, 40)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{70, 40, 40, 100\}$。
• 擦除 $x = 70$，写入 $(y, z) = (40, 40)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{40, 40, 40, 40, 100\}$。
• 擦除 $x = 100$，写入 $(y, z) = (40, 70)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{40, 40, 40, 40, 40, 70\}$。
• 擦除 $x = 70$，写入 $(y, z) = (40, 40)$。注意 $y+z = x + k$。此时黑板上的多重集为 $\{40, 40, 40, 40, 40, 40, 40\}$。

在第四个和第五个测试用例中，可以证明：无法使黑板上的所有数字相等。