背景

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。

3
3 5
1 2 5
4 10
1 3 3 7
1 2
2

Yes
No
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 组。只有通过某组全部测试点，且通过所有必需的前置组，才能获得该组分数。