本文主要是介绍Codeforces Round #775 (Div. 2) D，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

D. Integral Array

正向不好做 我们考虑反着做
我们知道一个数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);
}

这篇关于Codeforces Round #775 (Div. 2) D的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！