22年蓝桥杯国赛I题

题目大意：给定n个数和m次询问，每次询问给定一个值x，
问是否能在n个数中找出任意两个使得 a * x = b,也就是找倍数。
数据范围： 2 < n <= 200000, m <= 200000，每个数 x <= 200000

由于要询问m次，在询问里面操作一定不太行，所以只能通过预处理的方式，在进行询问操作

因为要找倍数，而且数字很小，我们先可以记录下每个数字出现的次数，然后通过制造倍数数组（确定每个倍数是否出现过），就可以利用nlogn的预处理时复AC了

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

int n,m;
int a[N],cnt[N],suc[N];

void work()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        cnt[a[i]] ++;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i ++)
    {
        if(i > 1 && a[i] == a[i - 1]) continue;
        for(int j =  a[i]; j <= a[n]; j += a[i])//寻找倍数
        {
            if(!cnt[j]) continue;//这一点没有，则直接跳过
            if(j == a[i] && cnt[j] < 2) continue;//确定1的倍数，只能是自己，所以出现次数要大于等于2次
            suc[j / a[i]] = 1;
        }
    }
    while(m --)
    {
        int x;
        cin >> x;
        if(suc[x]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    work();
    return 0;
}