B. Integral Array

B. Integral Array

题意：

对于一个序列a  如果对于任意ai aj  [ai / aj] 也在序列中 就称为好数组 

思路：

数据可达到1e6 显然暴力会超时

利用前缀和可以O(1) 地判断数字是否存在 序列中 记录每个数字的出现次数存到b数组中  然后再遍历1-c每次把b[i-1]加到b[i]中这样每个b[i]就是前缀和 即小于等于i的数的个数 

因为给定了最高界限 c 所以只要在c范围内讨论问题即可 

如果一个数x出现在数列中 而另一个数y没有出现在数列中 而它两的乘积x*y却出现在序列中 那么说明[x*y/x]不在序列中所以要输出no

 因为是向下取整 所以要判断[x * y, x * (y + 1))之间的数 

还有一些细节必须注意具体看代码注释

#include  
#define ll long long
#define pi acos(-1)
#define F ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
ll  n, c, a[N], b[N], pre[N];
 
void solve(){
    cin >> n >> c;
    for(int i = 1; i <= c; i++){
        b[i] = 0;
    }
    int flag = 1; 
    for(ll i = 1; i <= n; i++){  
        cin >> a[i];
        b[a[i]] ++;
    }  
    sort(a + 1, a + n + 1);
    //如果 序列中没有1就输出 no 
    if(a[1] != 1) {
        cout << "No\n";
        return;
    } 
    //将b数组变成 前缀和 即b[i]表示小于等于i的数的个数  
    for(ll i = 1; i <= c; i++){
        b[i] += b[i - 1]; 
    } 
    for(ll i = 1; i <= c; i++){  
        if(b[i] - b[i - 1]) continue;//i代表  序列中不存在的 
        
        //j代表序列中存在的 但是要注意不要用a[j] 来找存在的数会超时 
        //因为可能序列中每个数都一样且很小 而对于同一个数我们只要计算一次就好 
        //以下注释是错误示例 
        /*
        for(ll j = 1; j <= n; j ++) ... i * a[j]
        */
        for(ll j = 1; j <= c; j++){
            //大于c 直接退出  
            if(i * j > c) break;
            if(!(b[j] - b[j - 1])) continue;
            //右边界比c大时 应该取c  
            if(b[min((i + 1) * j - 1, c)] - b[i * j - 1] > 0) {
                flag = 0;
                break;
            }
        }
        if(!flag) break;
    }
    if(!flag) cout << "No\n";
    else cout << "Yes\n";
    return;
}
  
int main()
{
    F; 
    int t;
    cin >> t;
    while(t--){ 
        solve();
    }
 
    return 0;
}