题目链接：

把所有询问离线处理。

从右往左扫一遍，设\(p_i\)表示目前扫过的数中含有因子\(i\)的最左边的数的下标。

对当前的数\(a_i\)，扫描所有\(a_i\)的因子\(x\)，那么将所有\(x|a_j(j\ge i)\)的\(j\)，开一个数组\(c\)，将\(c_j\)与\(x\)取\(max\)，那么若当前有询问\([i,r]\)，则答案为\(\max_{k=1}^r\limits c_k\)。

显然，若有多个\(j\)，满足\(x|a_j\)，那么右端的没有最左端的优，所以只用更新\(c_{p_x}\)，同时更新\(p_x\)。

然后查询前缀\(max\)用树状数组即可。

因为\(a\)是个排列，所有因子总数约为\(O(n\ln n)\)

时间复杂度 \(O(n\ln nlog_2n)\)

瞎写蜜汁\(rk7\)，卡一卡应该很容易\(rk1\)开O2

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        inline int Min(const int a,const int b){return a
        
         b?a:b;}int t,n,a[50005],q,c[50005],Ans[50005],p[50005];std::vector
         
           Fra[50005];std::vector
          
           
             >Que[50005];//储存以当前点为左端的询问，一个是右端点，一个是询问的IDinline void Update(int x,const int v){if(x)for(;x<=n;x+=x&-x)c[x]=Max(c[x],v);}inline int Query(int x){int Res=0;for(;x;x^=x&-x)Res=Max(Res,c[x]);return Res;}int main(){ for(int i=1;i<=50000;++i) for(int j=i;j<=50000;j+=i) Fra[j].push_back(i);//预处理因子 for(scanf("%d",&t);t--;) { scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&a[i]),Que[i].clear(); scanf("%d",&q); for(int l,r,i=1;i<=q;++i) { scanf("%d%d",&l,&r); Que[l].push_back(std::make_pair(r,i)); } memset(c,0,sizeof c),memset(p,0,sizeof p); for(int i=n;i>=1;--i) { for(int j=0;j<(int)Fra[a[i]].size();++j) { Update(p[Fra[a[i]][j]],Fra[a[i]][j]); p[Fra[a[i]][j]]=i; }//先更新后查询 for(int j=0;j<(int)Que[i].size();++j) Ans[Que[i][j].second]=Query(Que[i][j].first); } for(int i=1;i<=q;++i)printf("%d\n",Ans[i]); } return 0;}