分解约数，O(n^1.5)

原题题意转换为，对每个询问x，查询序列中是否存在两个整数a,b，使得a/b=x（特别地，当只有一个齿轮时，x可以为1）

可以直接对所有结果为"YES"的x进行预处理。首先若b可被a整除，那么必有a<=b，且a是b的约数。将原序列排序后，从左到右分解约数x，然后查询这个约数是否在原序列中存在过。若是，那么标记x，查询到它时输出“YES”。


参考代码:（比赛时的源码，赛后AC）

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+5;

int ar[maxn],tag[maxn];

int res[maxn];

int main()

{

    int n,m;

    cin>>n>>m;

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

    {

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

    }

    sort(ar,ar+n);

    for(int i=0;i<n;++i){

        int t=ar[i];

        int up=sqrt(t);

        for(int j=1;j<=up;++j)

        {

            if(t%j==0)

            {

            if(tag[j])

            res[t/j]=1;

            if(tag[t/j])

            res[j]=1;

            }

        }

        tag[t]=1;

    }

    res[1]=1;

    while(m--)

    {

        int q;

        scanf("%d",&q);

        if(res[q])

        printf("YES\n");

        else

        printf("NO\n");

    }

    return 0;

}