题目大意

给出一个数列$A:a_1,a_2,a_3 \cdots a_n$

执行$m$次询问，每次给出区间$[l,r]$

在$[a_l,a_r]$中选一个数$x$

在$[a_1,a_{l-1}]$或者$[a_{r+1},a_n]$中选一个数$y$

求$gcd(x,y)$最大

数据范围

$n,m\leqslant 10^5,\max(a_1,a_2,a_3 \cdots a_n)\leqslant 10^5$

题解

戳我

程序

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Ford(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,tot,lastpos;
struct data{int l,r,id;}q[100500];
int t[400500];
int a[100500],ans[100500];
int pos[100500][150],dvs[100500][150],last[100500];
inline bool cmp1(data a,data b){return a.l<b.l;}
inline bool cmp2(data a,data b){return a.r>b.r;}

inline void insert(int p,int l,int r,int x,int c){
    if (l==r) {t[p]=max(t[p],c);return;}
    int mid=(l+r)>>1;
    if (x<=mid) insert(p<<1,l,mid,x,c);
    if (x>mid) insert(p<<1|1,mid+1,r,x,c);
    t[p]=max(t[p<<1],t[p<<1|1]);
}
inline int ask(int p,int l,int r,int x,int y){
    if (l==x&&r==y) return t[p];
    int mid=(l+r)>>1,sum=0;
    if (x<=mid) sum=ask(p<<1,l,mid,x,min(mid,y));
    if (y>mid) sum=max(sum,ask(p<<1|1,mid+1,r,max(mid+1,x),y));
    return sum;
}

inline void solve1(){
    Ford(i,n,1){
        tot=0;
        For(j,1,(int)sqrt(a[i]))
            if (a[i]%j==0){
                pos[i][++tot]=last[j],last[j]=i;
                dvs[i][tot]=j;
                int k=a[i]/j;
                if (j!=k){
                    pos[i][++tot]=last[k],last[k]=i;
                    dvs[i][tot]=k;
                }
            }
        dvs[i][0]=tot;
    }

    sort(q+1,q+m+1,cmp1),lastpos=1;
    For(i,1,m){
        For(j,lastpos,q[i].l-1) For(k,1,dvs[j][0])
            if (pos[j][k]) insert(1,1,n,pos[j][k],dvs[j][k]);
        ans[q[i].id]=ask(1,1,n,q[i].l,q[i].r);
        lastpos=q[i].l;
    }
}
inline void solve2(){
    memset(last,0,sizeof(last));
    memset(pos,0,sizeof(pos));
    memset(t,0,sizeof(t));

    For(i,1,n) For(j,1,dvs[i][0]){
        pos[i][j]=last[dvs[i][j]],last[dvs[i][j]]=i;
    }

    sort(q+1,q+m+1,cmp2),lastpos=n;
    For(i,1,m){
        Ford(j,lastpos,q[i].r+1) For(k,1,dvs[j][0])
            if (pos[j][k]) insert(1,1,n,pos[j][k],dvs[j][k]);
        ans[q[i].id]=max(ans[q[i].id],ask(1,1,n,q[i].l,q[i].r));
        lastpos=q[i].r;
    }  
}
int main(){
    n=read();
    For(i,1,n) a[i]=read();
    m=read();
    For(i,1,m) q[i]=(data){read(),read(),i};
    solve1();solve2();
    For(i,1,m) printf("%d\n",ans[i]);
    return 0;
}