题意：给一串数字，每次查询[L,R]中两个数的gcd的最大值。
解法：容易知道，要使取两个数让gcd最大，这两个数最好是倍数关系，所以处理出每个数的所有倍数，两两间根据倍数关系形成一条线段，值为该数。那么每次查询[L,R]之间两数gcd的最大值即为查询[L,R]中值最大的线段，离线所有的查询数据，然后按右端点坐标从小到大排序，依次往右加入即可。
这里学到了树状数组维护最大值的写法。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50007 int c[N];
struct node
{
int l,r,v;
}a[*N],Q[N];
int n,pos[N],num[N],ans[N]; int cmp(node ka,node kb) { return ka.r < kb.r; }
int lowbit(int x) { return x&-x; } void modify(int x,int val)
{
while(x > )
{
c[x] = max(c[x],val);
x -= lowbit(x);
}
} int getmax(int x)
{
int res = ;
while(x <= n)
{
res = max(res,c[x]);
x += lowbit(x);
}
return res;
} int main()
{
int t,i,j,x,q,tot;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&x);
pos[x] = i;
c[i] = ;
}
tot = ;
for(i=;i<=n/;i++)
{
int k = ;
for(j=i;j<=n;j+=i) //i的倍数
num[k++] = pos[j];
sort(num,num+k);
for(j=;j<k;j++)
{
a[tot].l = num[j-];
a[tot].r = num[j];
a[tot++].v = i;
}
}
scanf("%d",&q);
for(i=;i<q;i++)
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].v = i;
}
sort(a,a+tot,cmp);
sort(Q,Q+q,cmp);
j = ;
for(i=;i<q;i++)
{
if(Q[i].l == Q[i].r)
{
ans[Q[i].v] = ;
continue;
}
while(j < tot && a[j].r <= Q[i].r)
modify(a[j].l,a[j].v),j++;
ans[Q[i].v] = getmax(Q[i].l);
}
for(i=;i<q;i++)
printf("%d\n",ans[i]);
}
return ;
}