P13546 [OOI 2022] Integral Array

CF1648B

给定一个长度为 $n$ 的正整数数组 $a$，编号从 $1$ 到 $n$。我们称一个数组为**整性数组**，如果对于数组中任意两个（可以相同）数 $x$ 和 $y$，且 $x \ge y$，都有 $\left\lfloor \frac{x}{y} \right\rfloor$（即 $x$ 整除 $y$ 的向下取整）也在数组中。 保证所有 $a$ 中的数都不超过 $c$。你的任务是判断给定的数组是否为整性数组。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $c$（$1 \le n \le 10^6$，$1 \le c \le 10^7$），分别表示数组大小和数组元素的最大值。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le c$），表示数组 $a$。 记 $N$ 为所有测试数据中 $n$ 的总和，$C$ 为所有测试数据中 $c$ 的总和。保证 $N \le 10^6$ 且 $C \le 10^7$。

对于每组测试数据，若数组是整性数组，输出 `Yes`，否则输出 `No`。

### 说明 在第一个测试样例中，可以验证数组是整性的： - $\left\lfloor \frac{1}{1} \right\rfloor = 1$，$a_1 = 1$，该数在数组中 - $\left\lfloor \frac{2}{2} \right\rfloor = 1$ - $\left\lfloor \frac{5}{5} \right\rfloor = 1$ - $\left\lfloor \frac{2}{1} \right\rfloor = 2$，$a_2 = 2$，该数在数组中 - $\left\lfloor \frac{5}{1} \right\rfloor = 5$，$a_3 = 5$，该数在数组中 - $\left\lfloor \frac{5}{2} \right\rfloor = 2$，$a_2 = 2$，该数在数组中 因此该数组满足条件，是整性数组。 在第二个测试样例中，$\left\lfloor \frac{7}{3} \right\rfloor = 2$，但 $2$ 不在 $a$ 中，因此不是整性数组。 在第三个测试样例中，$\left\lfloor \frac{2}{2} \right\rfloor = 1$，但数组中只有 $2$，没有 $1$，因此不是整性数组。 ### 评分说明 本题测试数据分为 7 组。只有通过某组全部测试点，且通过所有必需的前置组，才能获得该组分数。 | 组别 | 分值 | $N$ | $C$ | 必须通过的组 | 备注 | |:----:|:----:|:---:|:---:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | 样例测试点 | | 1 | 13 | $N \le 100$ | -- | 0 | | | | 2 | 17 | $N \le 100\,000$ | $C \le 10\,000$ | 0 | | | 3 | 15 | $N \le 1000$ | -- | 0, 1 | | | | 4 | 27 | $N \le 100\,000$ | -- | 0--3 | | | | 5 | 28 | -- | -- | 0--4 | | |