题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4630
题意：给你N个数，然后给你M个询问，每个询问包含一个l 一个r，问你lr 这个区间中任意两个数最大的公约数。
思路:以为是l,r所以，只跟l后面的有关，所以把询问排序，数组a[]从后往前枚举约数，标记下这个约数最早出现的位置，如果这个约数出现了，那就让这个数更新一下最大的保存在树状数组中，如果没出现，那么就标记一下位置就好~这样的后面的答案会影响前面的但是前面的不会影响后面的。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
using namespace std;
struct node
{
int l,r,num;
}q[];
int n;
int cmp(const struct node a,const struct node b)
{
return a.l > b.l;
} int a[];
int pre[];
int c[]; void update(int x,int d)
{
while(x <= n)
{
c[x] = max(c[x],d);
x += lowbit(x);
}
} int getres(int x)
{
int res = ;
while(x > )
{
res = max(c[x],res);
x -= lowbit(x);
} return res; }
int ans[];
int main()
{
int t; while (~scanf("%d",&t))
{ while(t--)
{
int cnt = ;
scanf("%d",&n);
int i,j;
loop(,i,n+)
scanf("%d",&a[i]); int m;
scanf("%d",&m); loop(,i,m)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].num = i;
} sort(q,q+m,cmp); cl(c,);
cl(pre,-); for(i = n;i > ; i--)
{
for(j = ;j*j <= a[i];j++)
{
if(a[i]%j == )
{
if(pre[j] != -)
update(pre[j],j); pre[j] = i; if(j != (a[i]/j))
{
if(pre[a[i]/j] != -)
update(pre[a[i]/j],a[i]/j);
pre[a[i]/j] = i;
}
}
}
while(cnt < m && q[cnt].l == i)
{
ans[q[cnt].num] = getres(q[cnt].r);
cnt++;
}
} loop(,i,m)
printf("%d\n",ans[i]);
}
}
return ;
}