题目链接：https://ac.nowcoder.com/acm/contest/4090/E
题目大意：

思路：我们可以证明一定是一个区间里面的a[i]与X。你们问题就转化成给你一个区间[L, R]找到一个L<=i<=R。最大化gcd(a[i], X)。因为最大GCD一定是X的因数。可以直接莫队维护一个区间%P的个数。

题解思路：

//莫队
#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int a[100005], f[100005], ans[100005];
int pos[100005];
vector<int> v[100005];
vector<int> qu[100005];
 
struct Q{
    int l, r, x, i;
}q[100005];
 
void add(int x){
    for(auto u: v[x]){
        f[u]++;
    }
}
 
void del(int x){
    for(auto u: v[x]){
        f[u]--;
    }
}
 
int main(){
    int n, m;scanf("%d%d", &n, &m);
    int Len=sqrt(n);
    for(int i=1; i<=n; i++){
        pos[i]=i/Len;
        scanf("%d", &a[i]);
        for(int j=1; j*j<=a[i]; j++){
            if(a[i]%j==0){
                v[i].push_back(j);
                if(j!=a[i]/j){
                    v[i].push_back(a[i]/j);
                }
            }
        }
    }
 
 
 
    for(int i=1; i<=m; i++){
        int l, r, x;
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].x);
        for(int j=1; j*j<=q[i].x; j++){
            if(q[i].x%j==0){
                qu[i].push_back(j);
                if(j!=q[i].x/j){
                    qu[i].push_back(q[i].x/j);
                }
            }
        }
        sort(qu[i].begin(), qu[i].end(), greater<int>() );
 
        q[i].i=i;
 
    }
 
    sort(q+1, q+1+m, [](Q a, Q b){return pos[a.l]==pos[b.l]?(pos[a.l]&1)?a.r<b.r:a.r>b.r:pos[a.l]<pos[b.l];});
    int L=1, R=0;
    for(int i=1;i<=m;i++)
    {
        while(L<q[i].l)
        {
            del(L);
            L++;
        }
        while(L>q[i].l)
        {
            L--;
            add(L);
        }
        while(R<q[i].r)
        {
            R++;
            add(R);
        }
        while(R>q[i].r)
        {
            del(R);
            R--;
        }
        for(auto u: qu[q[i].i]){
            if(f[u]){
                ans[q[i].i]=u;
                break;
            }
        }
 
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",ans[i]);
    }
 
    return 0;
}

//离线-区间处理
#include<bits/stdc++.h>
#define LL long long
using namespace std;

int a[100005], ans[100005];
struct node{
    int l, r, i;
    bool operator<(const node &a) const{
        return r<a.r;
    }
};
vector<int> v[100005];
vector<node> q[100005];

int main(){
    int n, m;scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        for(int j=1; j*j<=a[i]; j++){
            if(a[i]%j==0){
                v[j].push_back(i);
                if(j!=a[i]/j){
                    v[a[i]/j].push_back(i);
                }
            }
        }
    }

    for(int i=1; i<=m; i++){
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        for(int j=1; j*j<=x; j++){
            if(x%j==0){
                q[j].push_back(node{l, r, i});
                if(j!=x/j){
                    q[x/j].push_back(node{l, r, i});
                }
            }
        }
    }
    for(int i=1; i<=100000; i++){
        if(!v[i].size()){
            continue;
        }
        int k=0;
        sort(q[i].begin(), q[i].end());

        while(k<q[i].size()&&q[i][k].r<v[i][0]) k++;
        for(int j=0; j<v[i].size()-1; j++){
            while(k<q[i].size()&&q[i][k].r<v[i][j+1]){
                if(q[i][k].l<=v[i][j]){
                    ans[q[i][k].i]=max(ans[q[i][k].i], i);
                }
                k++;
            }
        }
        while(k<q[i].size()){
            if(q[i][k].l<=v[i][v[i].size()-1])
                ans[q[i][k].i]=max(ans[q[i][k].i],i);
            k++;
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }

    return 0;
}