← 返回题目列表

Codeforces · 1648/B

B. 积分阵列

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 正整数,编号从 $$$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^6$$$) - $$$a$$$ 的大小和数组中数字的限制。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le c$$$) - 数组 $$$a$$$。

令 $$$N$$$ 为所有测试用例的 $$$n$$$ 之和,$$$C$$$ 为所有测试用例的 $$$c$$$ 之和。保证 $$$N \le 10^6$$$ 和 $$$C \le 10^6$$$。

输出

对于每个测试用例,如果数组是整数,则打印“是”,否则打印“否”。

示例

输入 #1

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

输出 #1

Yes
No
No
Yes

输入 #2

1
1 1000000
1000000

输出 #2

No

注意

在第一个测试用例中,很容易看出该数组是整数:

- $$$\left \lfloor \frac{1}{1} \right \rfloor = 1$$$, $$$a_1 = 1$$$,此数字出现在 arry 中
- $$$\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 = \left \lfloor 2\frac{1}{3} \right \rfloor = 2$$$,这个数字不在$$$a$$$中,这就是为什么它不是整数。

在第三个测试用例中 $$$\left \lfloor \frac{2}{2} \right \rfloor = 1$$$,但数组中只有 $$$2$$$,这就是为什么它不是整数。