CF1648B Integral Array

题目描述

You are given an array aa of nn positive integers numbered from 11 to nn . Let's call an array integral if for any two, not necessarily different, numbers xx and yy from this array, x \ge yx≥y , the number \left \lfloor \frac{x}{y} \right \rfloor⌊yx​⌋ ( xx divided by yy with rounding down) is also in this array.

You are guaranteed that all numbers in aa do not exceed cc . Your task is to check whether this array is integral.

输入格式

The input consists of multiple test cases. The first line contains a single integer tt ( 1 \le t \le 10^41≤t≤104 ) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers nn and cc ( 1 \le n \le 10^61≤n≤106 , 1 \le c \le 10^61≤c≤106 ) — the size of aa and the limit for the numbers in the array.

The second line of each test case contains nn integers a_1a1​ , a_2a2​ , ..., a_nan​ ( 1 \le a_i \le c1≤ai​≤c ) — the array aa .

Let NN be the sum of nn over all test cases and CC be the sum of cc over all test cases. It is guaranteed that N \le 10^6N≤106 and C \le 10^6C≤106 .

输出格式

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

题意翻译

题意 ： 给定一个数组 \ a a , 我们称该数组完整需要满足 ：若数组\ a a 中存在两数 \ x,y\ \ x,y  , 使 \ y \le x\ \ y≤x  (\ x,y\ x,y  可以是同一个数) , 则\left\lfloor\dfrac{x}{y}\right\rfloor⌊yx​⌋也必须在数组\ a a 中 , 现需要判断数组\ a a 是否完整 。

\ T\le 10^4 ,\sum n\le 10^6,\sum c\le 10^6 T≤104,∑n≤106,∑c≤106 , 其中\ T T 为数据组数 ， \ n n 为\ a a 的元素个数，满足\ a a 中元素\le c≤c 。

输入输出样例

输入 #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⌊11​⌋=1 , a_1 = 1a1​=1 , this number occurs in the arry
• \left \lfloor \frac{2}{2} \right \rfloor = 1⌊22​⌋=1
• \left \lfloor \frac{5}{5} \right \rfloor = 1⌊55​⌋=1
• \left \lfloor \frac{2}{1} \right \rfloor = 2⌊12​⌋=2 , a_2 = 2a2​=2 , this number occurs in the array
• \left \lfloor \frac{5}{1} \right \rfloor = 5⌊15​⌋=5 , a_3 = 5a3​=5 , this number occurs in the array
• \left \lfloor \frac{5}{2} \right \rfloor = 2⌊25​⌋=2 , a_2 = 2a2​=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⌊37​⌋=⌊231​⌋=2 , this number is not in aa , that's why it is not integral.

In the third test case \left \lfloor \frac{2}{2} \right \rfloor = 1⌊22​⌋=1 , but there is only 22 in the array, that's why it is not integral.

 题意：任选两个数x，y（可能是同一个，也可能是不同的），看对任意的xy（x>=y），x/y下取整是否在数组里出现过，如果出现过就符合题意，只要有一组没出现就输出no。

思路：暴力肯定会t，那么我们就反着来想，假设x/y=i，x的范围就是y*i<=x<y*(i+1)，我们选一个在数组中的数y和一个不在数组中的数i，那么得到的x应该是不在数组中的，即在y*i<=x<y*(i+1)这个范围内没有数在数组中。

那么我们要处理这个问题的话，用一个数组来记录一下一个数有没有在数组中出现过，先出现过试1，没出现过是0，那么我们先遍历一遍1~c，找到一个i表示出现过的数之后，再遍历一遍1~c，找一个j表示没有出现过的数，那么由他们算出的x就不可能出现在这个数组，即y*i<=x<=y*(i+1)-1这段的子段和是0.如果大于0的话不符合题意，直接输出no，注意边界问题，我们找的时候因为找i*j，所以当进行j的循环的时候，条件就可以设置为i*k<=c,当算出y*(i+1)-1这个右边界的时候，我们要拿他和c比较取最小值。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
const int N=1000005;
typedef long long ll;
int n,c;
int s[N],a[N];
void sove(){
	cin>>n>>c;
	for(int i=1;i<=c;i++){
		a[i]=s[i]=0;
	}
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		a[x]=1;
	}
	for(int i=1;i<=c;i++)s[i]=s[i-1]+a[i];
	for(int i=1;i<=c;i++){
		if(a[i]==0)continue;
		for(int j=1;i*j<=c;j++){
			if(a[j]==1)continue;
			int l=i*j-1;
			int r=min(c,i*(j+1)-1);
			if(s[r]-s[l]>0){
				cout<<"No"<<endl;
				return ;
			}
		}
	}
	cout<<"Yes"<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	int t;
	cin>>t;
	while(t--){
		sove();
	}
	return 0;
}