正向不好做 我们考虑反着做
我们知道一个数x下取整 要是有k和x两个数的话[kx,kx+x-1]
我们能考虑到这样区间赋值 利用线段树可以做到O(clogc)
还有O(clogc)的做法就是暴力的来对于每一个x都遍历一遍其倍数 要是其倍数有值 那么我们必须拥有其倍数才行 否则NO
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
//do O(1)
}
}
这行代码是个级数 复杂度是O(nlogn)的 高数教过
#include <bits/stdc++.h> using namespace std; const int N = 2e5+10; const int M = 998244353; const int mod = 1000000007; #define int long long #define endl '\n' #define Endl '\n' #define YES cout<<"Yes"<<endl; #define NO cout<<"No"<<endl; #define _ 0 #define inf 0x3f3f3f3f3f3f3f3f #define fast ios::sync_with_stdio(false);cin.tie(nullptr); void solve() { int n,c;cin>>n>>c; vector<int>a(n+1),pre(c+1),loc(c+1); for(int i=1;i<=n;i++)cin>>a[i],loc[a[i]]++; for(int i=1;i<=c;i++)pre[i]=pre[i-1]+loc[i]; for(int i=1;i<=c;i++){ if(!loc[i])continue; for(int j=i;j<=c;j+=i){ int l=j,r=min(c,j+i-1); if(pre[r]-pre[l-1]>0&&loc[j/i]==0){NO return;} } } YES } signed main(){ fast int T;cin>>T; while(T--) { solve(); } return ~~(0^_^0); }