蓝桥杯2022年第十三届决赛真题-齿轮(复杂度O(qlnq))

解题思路:
枚举所有倍数下的所有半径，判断是否存在两个半径为此倍数。
注意事项:
枚举半径只到max(qi,ri)/i,总共进行∑q/i次，类比调和级数调，故复杂度近似O(qlnq)。
参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxx 221200

#define int long long

int n,m,a,b,q;

int all[maxx];

int cha[maxx];

unordered_map<int,int> M;

signed main()

{

    scanf("%lld %lld",&n,&q);

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

    {scanf("%lld",&all[i]);

    m=max(m,all[i]);

    M[all[i]]=1;}

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

    for(int j=1;j<=m/i;++j)

    if(M.count(j*i)==1&&M.count(j)==1) cha[i]=1;

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

     {scanf("%lld",&a);

     if(cha[a]==1)  cout<<"YES"<<"\n";

     else cout<<"NO"<<"\n";

     }

}