[数据结构与算法]cf Round #775 Div.2 -D【逆向思维+简单数学】

Date：2022.03.06
题意：给一个数组，是否能满足其中任意两个元素x>=y保证$?\frac{x}{y}?$存在于数组中。

思路：打表每个数的倍数（保证<=最大值），找性质。以样例中的1 3 3 7为例，打表如下：
1 2 3 4 5 6 7
3 6
3 6
7
我们再以3 6为例，分别是$3\times 1、3\times 2$，这里的1、2即代表数组中是否能有数$?$使得$?/3==1、2$，且$1、2$也在数组中【否则不合法】？我们再以$?/3==2$为例，显然$?\in [2\times 3,2\times 3+2]$，因此问题转换为：判断每个数$a[i]$的所有倍数$x(<=c)$在对应的$[x,min(c,x+a[i]?1)]$区间下是否有至少$1$个数$x^{\prime }$（有数才能继续判断$x^{\prime }/a[i]$是否在数组中），使得$x^{\prime }/a[i]$也在数组中，若不在则不合法（即产生了不存在于数组中的值）。判断区间是否有至少1个数就乱搞一个前缀和判定区间中有几个元素存在于数组中即可。
至于复杂度，由于$c/1+c/2+c/3+...+c/c$，调和级数大概是$O(c?ln(c+1))$。
此外，记得去重，重复元素显然毫无意义，不然tle14。

代码如下：

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
const LL N = 2e6+10,INF=0x3f3f3f3f3f3f3f3f;
typedef pair<LL, LL> PII;
LL t,n,m,k,a[N],c,cnt[N];
LL st[N],sumst[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>c;
        for(int i=1;i<=c;++i) {cnt[i]=0;st[i]=0;sumst[i]=0;}
        for(int i=1;i<=n;++i) {cin>>a[i];st[a[i]]=1;}
        for(int i=1;i<=c;++i) sumst[i]=sumst[i-1]+st[i];
        sort(a+1,a+1+n);LL len=unique(a+1,a+1+n)-a-1;
        bool flag=true;
        if(a[1]!=1) {cout<<"No"<<endl;continue;}
        for(int i=1;i<=len;++i)
        {
            for(int x=a[i],j=1;x<=c;x+=a[i],++j)
            {
                if(st[x/a[i]]) continue;
                if(sumst[min(x+a[i]-1,c)]-sumst[x-1]>0)//注意右边界不要越界，不然初始化比较难办
                {
                    if(!st[j]) {flag=false;break;}
                }
            }
            if(!flag) break;
        }
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}