自动搬运

查看原文

来自洛谷，原作者为

	cwfxlh 会赢的！

搬运于2025-08-24 22:42:35，当前版本为作者最后更新于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;
}