[数据结构与算法]D. Integral Array

题目

大意

给一个序列$a$，如果对任意 $x<y$ 使得 $\frac{x}{y}$ 也在序列 $a$ 中 则输出YES，否则NO

思路

考虑到 $\frac{x}{y}$ = k 那么 x 的取值范围为 $[k?y,(k+1)?y)$，那么可以暴力枚举$y$以及其倍数$k$，利用$x$个数的前缀和来判断在$x$的取值范围内是否存在一个$x$,，若存在再判断$k$是否在序列中,不存在则输出 $no$,否则输出 $yes$

code

// Problem: D. Integral Array
// Contest: Codeforces - Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/contest/1649/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define _orz ios::sync_with_stdio(false),cin.tie(0)
#define mem(str,num) memset(str,num,sizeof(str))
#define forr(i,a,b) for(int i = a;i <= b;i++)
#define forn(i,n) for(int i = 0; i < n; i++)
#define all(a) (a.begin(),a.end())
#define dbg() cout << "0k!" << endl;
//#define _DEBUG
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6+10;
const ll MOD = 1e9+7;


void so1ve(){
	int n,c;
	cin >> n >> c;
	vector<int> a(c+1),sum(c+1);
	forr(i,1,n){
		int x;cin >> x;
		a[x]++;
	}
	forr(i,1,c){
		sum[i] = sum[i-1] + a[i];
	}
	forr(i,1,c){
		if(!a[i]) continue;
		
		for(int j = 1; j*i <= c;j++){
			int r = min(c,j*i+i-1);
			if(sum[r] - sum[j*i-1] > 0){
				if(a[j] == 0) {
					cout <<"No\n";
					return;
				}
			}
		}
	}
	cout <<"Yes\n";
	
}
int main()
{
#ifdef _DEBUG
    //freopen("input.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int t; cin >> t;
    while(t--) so1ve();
    return 0;
}