本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-13 13:17:11

题目大意：

给定 $n$ 和 $c$。
给定一个长度为 $n$ 的数组 $a (1 \le a_i \le c$) 。有以下规则：
数组中拿出任意两个数 $x,y (y \le x)$，如果 $\lfloor \frac{x}{y} \rfloor$ 也存在于数组中，那么称这个数组是完美的。
问 $a$ 数组是不是完美的。
$1 \le n \le 10^6$
$1 \le c \le 10^6$

题目分析：

可以发现，题目限定了每个数组元素 $a_i \le c$,也就是说 $a_i$ 不会超过 $10^6$，可以用一种类似于线性筛的方法求解。
枚举 $i$ 从 $2$ 到 $n$，作为除数。里面再套一层枚举 $j$ 作为商 $(i \cdot j \le c)$。此时被除数的范围是 $(i \cdot j,i \cdot j + i-1)$。显然，如果数组中的某一个数在当前被除数范围中，并且数组中不存在商 $j$，那么数组 $a$ 就不是完美的。

那么如何判断某个数值范围内是否有数出现在 $a$ 中呢，可以使用前缀和的方法。定义一个数组 $hash$,记录 $a$ 中每一个值出现次数，代码如下：

for(int i=1;i<=n;i++)
{
    a[i]=read();
    hash[a[i]]++;
}

然后定义一个数组 $qzh$，$qzh_i$ 代表 $1$ 到 $i$ 的所有数字在 $a$ 中的出现次数。假设被除数数值范围是 $(l,r)$，如果 $qzh[r]-qzh_{l-1}$ 的值为 $0$，那么说明数组 $a$ 没有一个元素在被除数数值范围内，否则说明数组 $a$ 至少有一个元素在被除数数值范围内。

AC 代码：

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e6+5;
namespace Main
{
    inline int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while(!isdigit(ch))
        {
            if(ch=='-')f=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*f;
    }
    int hash[maxn];
    int qzh[maxn];
    int a[maxn];
    bool vis[maxn];
    int t;
    int n,c;
    void main()
    {
        t=read();
        while(t--)
        {
            n=read();
            c=read();
            for(int i=1;i<=n;i++)
            {
                a[i]=read();
                hash[a[i]]++;
                vis[a[i]]=1;
            }
            for(int i=1;i<=c;i++)
            {
                qzh[i]=qzh[i-1]+hash[i];
            }\/\/方便确定某一个范围内的数的数量
            bool flag=1;
            for(int i=2;i<=c;i++)
            {
                if(!vis[i])continue;
                for(int j=1;i*j<=c;j++)
                {\/\/枚举因数，跟线性筛有些像
                    int l=i*j;
                    int r=i*j+i-1;
                    r=min(r,c);
                    if((qzh[r]-qzh[l-1])&&!vis[j])
                    {
                        flag=0;
                    }
                }
            }
            if(!flag)
            {
                printf("No\n");
            }
            else
            {
                printf("Yes\n");
            }
            for(int i=1;i<=n;i++)
            {
                hash[a[i]]--;
                vis[a[i]]=0;
            }
        }
    }
}
int main()
{
    Main::main();
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}