CF1641A Great Sequence

对于一个正整数 $x$，如果一个正整数序列可以被划分为若干对，使得每一对中第一个数乘以 $x$ 等于第二个数，则称该序列对于 $x$ 是“great”的。更正式地说，长度为 $n$ 的序列 $a$ 对于正整数 $x$ 是 great 的，当且仅当 $n$ 是偶数，且存在一个长度为 $n$ 的排列 $p$，使得对于每个 $i$（$1 \le i \le \frac{n}{2}$），都有 $a_{p_{2i-1}} \cdot x = a_{p_{2i}}$。 Sam 有一个序列 $a$ 和一个正整数 $x$。请你帮助他使序列变为 great：求最少需要在序列 $a$ 的末尾添加多少个正整数，才能使其对于 $x$ 是 great 的。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 20000$），表示测试数据的组数。接下来每组测试数据描述如下： 每组测试数据的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 2 \times 10^5$，$2 \le x \le 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一个整数，表示最少需要在 $a$ 的末尾添加多少个正整数，才能使其对于 $x$ 是 great 的。

在第一个测试用例中，Sam 很幸运，序列已经对于 $4$ 是 great 的，因为可以将其划分为如下的配对：$(1, 4)$，$(4, 16)$。因此无需添加任何数字。 在第二个测试用例中，你可以向序列中添加 $1$ 和 $14$，然后可以将所有 $8$ 个整数划分为如下配对：$(1, 2)$，$(1, 2)$，$(2, 4)$，$(7, 14)$。无法通过添加更少的数字来使序列满足条件。 由 ChatGPT 4.1 翻译