#P12637. 「OOI 2022 Day 2」完整数组

「OOI 2022 Day 2」完整数组

题目描述

给定一个包含 nn 个正整数的数组 aa,元素编号从 11 到 nn。如果对于数组中任意两个(不一定不同)的数字 xx 和 yy,当 x≥yx \geq y 时,⌊xy⌋\left \lfloor \frac{x}{y} \right \rfloor(xx 除以 yy 的商,向下取整)也在该数组中,则称该数组为完整数组。

已知数组 aa 中的所有数字均不超过 cc。你的任务是检查给定数组是否为完整数组。

输入格式

每个测试点包含多组输入数据。第一行包含一个整数 tt (1≤t≤10000)(1 \leq t \leq 10000),表示输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含两个整数 nn 和 cc (1≤n≤106,1≤c≤107)(1 \leq n \leq 10^{6}, 1 \leq c \leq 10^{7}),分别表示数组 aa 的大小和数组中数字的上限。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤c)(1 \leq a_i \leq c),表示数组 aa 的元素。

设 NN 表示所有数据组中 nn 的总和,CC 表示所有数据组中 cc 的总和。保证 N≤106N \leq 10^{6} 且 C≤107C \leq 10^{7}。

输出格式

对于每组输入数据,如果数组是完整的输出 Yes,否则输出 No。

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

Yes
No
No

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 00 是样例。

子任务 分值 附加限制 子任务依赖 备注
11 1313 N≤100N \leq 100 00
22 1717 N≤100000N \leq 100000,C≤10000C \leq 10000 00
33 1515 N≤1000N \leq 1000 0,10, 1
44 2727 N≤100000N \leq 100000 0∼30 \sim 3
55 2828 0∼40 \sim 4