https://vjudge.net/problem/HDU-4630

code:

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
vector<int>v[N];
int n,m,a[N],pre[N],t[N],ans[N];
struct node{
	int l,r,id;
}q[N];
bool cmp(node x,node y){return x.l>y.l;}
int lb(int x){return x&(-x);}
int query(int x)
{int res=0;for(;x>=1;x-=lb(x))res=max(res,t[x]);return res;}
void update(int x,int y)
{for(;x<=n;x+=lb(x))t[x]=max(t[x],y);}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	for(int i=2;i<N;i++)
		for(int j=i;j<N;j+=i)
			v[j].push_back(i);
	int T;cin>>T;
	while(T--)
	{
		memset(t,0,sizeof(t));
		memset(pre,0,sizeof(pre));
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		cin>>m;
		for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
		sort(q+1,q+1+m,cmp);
		int it=n+1;
		for(int i=1;i<=m;i++)
		{
			for(it--;it>=q[i].l;it--)
				for(auto &j:v[a[it]])
				{
					if(pre[j])update(pre[j],j);
					pre[j]=it;
				}
			it++;
			if(q[i].l!=q[i].r)ans[q[i].id]=query(q[i].r);
			else ans[q[i].id]=0;
		}
		for(int i=1;i<=m;i++)
		cout<<ans[i]<<'\n';
	}
	return 0;
 }