309236: CF1648B. Integral Array

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Integral Array

题意翻译

题意 : 给定一个数组 $\ a $ , 我们称该数组完整需要满足 :若数组$\ a$ 中存在两数 $\ x,y\ \ $, 使 $\ y \le x\ \ $($\ x,y\ $ 可以是同一个数) , 则$\left\lfloor\dfrac{x}{y}\right\rfloor $也必须在数组$\ a$ 中 , 现需要判断数组$\ a$ 是否完整 。 $\ T\le 10^4 ,\sum n\le 10^6,\sum c\le 10^6 $ , 其中$\ T$ 为数据组数 , $\ n$ 为$\ a$ 的元素个数,满足$\ a $ 中元素$\le c$ 。

题目描述

You are given an array $ a $ of $ n $ positive integers numbered from $ 1 $ to $ n $ . Let's call an array integral if for any two, not necessarily different, numbers $ x $ and $ y $ from this array, $ x \ge y $ , the number $ \left \lfloor \frac{x}{y} \right \rfloor $ ( $ x $ divided by $ y $ with rounding down) is also in this array. You are guaranteed that all numbers in $ a $ do not exceed $ c $ . Your task is to check whether this array is integral.

输入输出格式

输入格式


The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ c $ ( $ 1 \le n \le 10^6 $ , $ 1 \le c \le 10^6 $ ) — the size of $ a $ and the limit for the numbers in the array. The second line of each test case contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \le a_i \le c $ ) — the array $ a $ . Let $ N $ be the sum of $ n $ over all test cases and $ C $ be the sum of $ c $ over all test cases. It is guaranteed that $ N \le 10^6 $ and $ C \le 10^6 $ .

输出格式


For each test case print Yes if the array is integral and No otherwise.

输入输出样例

输入样例 #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

说明

In the first test case it is easy to see that the array is integral: - $ \left \lfloor \frac{1}{1} \right \rfloor = 1 $ , $ a_1 = 1 $ , this number occurs in the 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 $ , this number occurs in the array - $ \left \lfloor \frac{5}{1} \right \rfloor = 5 $ , $ a_3 = 5 $ , this number occurs in the array - $ \left \lfloor \frac{5}{2} \right \rfloor = 2 $ , $ a_2 = 2 $ , this number occurs in the array Thus, the condition is met and the array is integral. In the second test case it is enough to see that $ \left \lfloor \frac{7}{3} \right \rfloor = \left \lfloor 2\frac{1}{3} \right \rfloor = 2 $ , this number is not in $ a $ , that's why it is not integral. In the third test case $ \left \lfloor \frac{2}{2} \right \rfloor = 1 $ , but there is only $ 2 $ in the array, that's why it is not integral.

Input

题意翻译

题意 : 给定一个数组 $\ a $ , 我们称该数组完整需要满足 :若数组$\ a$ 中存在两数 $\ x,y\ \ $, 使 $\ y \le x\ \ $($\ x,y\ $ 可以是同一个数) , 则$\left\lfloor\dfrac{x}{y}\right\rfloor $也必须在数组$\ a$ 中 , 现需要判断数组$\ a$ 是否完整 。 $\ T\le 10^4 ,\sum n\le 10^6,\sum c\le 10^6 $ , 其中$\ T$ 为数据组数 , $\ n$ 为$\ a$ 的元素个数,满足$\ a $ 中元素$\le c$ 。

加入题单

上一题 下一题 算法标签: