P8799

cwfxlh · 2022-11-29 13:08:07 · 题解

P8799

题目传送门

upd:2023 年 4 月 10 日的时候被 feecle6418 的加强数据橄榄了，所以重写一发。

首先，齿轮之间的半径很明显决定了它们的速度关系，两个咬合在一起的齿轮，它们的速度之比与它们的半径之比成反比。 也就是

那么，对于一系列连在一起的齿轮，

这个可以通过把比例乘起来得到，不多讲。
到了这里，题意就很清楚了，它要我们求出数列 a_{1...n} 中有没有一对数的比值为 q_i。

因为 Q 的范围过大，所以每次询问时进行处理不太可能，同时离线下来也没有什么帮助。所以考虑预处理答案。
对于每一个合法的 q_i，其必然可以表示为 \frac{a_i}{a_j} 的形式，则考虑枚举 a_j，便能做到 \Theta(n\log n) 级别的预处理，可以通过此题。

上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,k1,mp[300003],ans[300003],a[300003];
signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        mp[a[i]]++;
    }
    sort(a+1,a+n+1);
    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(!mp[j])continue;
            if(mp[j]==1&&j==a[i])continue;
            ans[j/a[i]]=1;
        }
    }
    while(q--){
        scanf("%lld",&k1);
        if(ans[k1]==1)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}