二分，

先离线处理所有因子他们对应的位置，只需要找一个值和x gcd就行了，把x因子放进一个数组里，排序，从x到1大到小进行枚举，查找是否存在在l到r之间有个值能满足该因子，存在直接输出答案break。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const    int    N=100010;
vector<int>vv[N];
int a[N];
int res[N];
void init(int x)
{
    for(int i=1;(ll)i*i<=a[x];i++)
    {
        if(a[x]%i==0)
        {
            vv[i].push_back(x);
            if(a[x]/i!=i)
            vv[a[x]/i].push_back(x);
        }    
    }
}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        init(i);
    while(q--)
    {
         int num=0;
       int l,r,x;
        cin>>l>>r>>x;
        for(int i=1;i*i<=x;i++)
            if(x%i==0)
            {  
			res[num++]=i;
                if(i*i!=x)
                res[num++]=x/i;
            } 
       sort(res,res+num); 
        for(int i=num-1;i>=0;i--)
        {
            int t=lower_bound(vv[res[i]].begin(),vv[res[i]].end(),l)-vv[res[i]].begin();
        //    printf("t=%d\n",t);
            if(t!=vv[res[i]].size()&&vv[res[i]][t]<=r)
            {
             cout<<res[i]<<endl;
                break;
            } 
        }
    }
    return 0;
}