蓝桥杯2022年第十三届决赛真题-齿轮

解题思路:
先把半径排序，把每个半径i进行约数分解，如果半径i的某个约数是之前出现过的半径j（j<=i）, 则i/j倍可行，由于i/j也是i的约数，所以j倍也可行。

注意事项:
输入要用scanf，用cin过不了
参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10,M=3e6+10;

int n,Q;

int r[N],q;

bool st[M];

unordered_set<int>s;

int main()

{

scanf("%d %d",&n,&Q);

for(int i=1;i<=n;i++)

scanf("%d",&r[i]);

sort(r+1,r+1+n);

for(int i=1;i<=n;i++)

{

int v=r[i];

for(int j=1;j<=v/j;j++)

{

if(v%j==0)

{

if(s.count(j))

{

st[v/j]=true;

}

if(s.count(v/j))

{

st[j]=true;

}

} 

}

s.insert(v);

}

while(Q--)

{

scanf("%d",&q);

if(n==1&&q==1) puts("YES");

else if(st[q]) puts("YES");

else  puts("NO");

}

return 0;

}