树状数组维护+离线

最大gcd一定是某个数的一个约数，对所有询问按右端点排序，用树状数组维护即可。。

具体做法：记录每个约数出现的上一个位置pre，对于左端点落在pre之前的询问这个约数就可能是答案，所以我们对pre向前进行维护，而询问的时候从左端点往上找最大值。。。。

No Pain No Game

1
10
8 2 4 9 5 7 10 6 1 3
5
2 10
2 4
6 9
1 4
7 10

5
2
2
4
3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=60000;

vector<int> fact[maxn];

void get_factor()
{
    for(int i=1;i<maxn;i++)
    {
        for(int j=i;j<maxn;j+=i)
        {
            fact[j].push_back(i);
        }
    }
}

int n,Q,T,tree[maxn],pre[maxn],arr[maxn],ans[maxn];

struct ASK
{
    int l,r,id;
}ask[maxn];

bool cmp(ASK a,ASK b)
{
   if(a.r!=b.r) return a.r<b.r;
   return a.l<b.l;
}

int lowbit(int x)
{
    return x&(-x);
}

void update(int p,int v) ///向下更新最大约数
{
    for(int i=p;i;i-=lowbit(i)) tree[i]=max(tree[i],v);
}

int query(int p)
{
    int ret=0;
    for(int i=p;i<maxn;i+=lowbit(i)) ret=max(ret,tree[i]);
    return ret;
}

int main()
{
    scanf("%d",&T);
    get_factor();
while(T--)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",arr+i);
    scanf("%d",&Q);
    for(int i=0;i<Q;i++)
    {
        scanf("%d%d",&ask[i].l,&ask[i].r); ask[i].id=i;
    }
    sort(ask,ask+Q,cmp);
    memset(tree,0,sizeof(tree));
    memset(pre,-1,sizeof(pre));
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int sz=fact[arr[i]].size(),j=0;j<sz;j++)
        {
            int fc=fact[arr[i]][j];
            if(pre[fc]!=-1)
            {
                update(pre[fc],fc);
            }
            pre[fc]=i;
        }
        while(cnt<Q&&ask[cnt].r==i)
        {
            ans[ask[cnt].id]=query(ask[cnt].l);
            cnt++;
        }
    }
    for(int i=0;i<Q;i++) printf("%d\n",ans[i]);
}
    return 0;
}

HDOJ 4630 No Pain No Game,布布扣,bubuko.com

HDOJ 4630 No Pain No Game

原文：http://blog.csdn.net/u012797220/article/details/22319041