线段树。
因为是取模运算，所以数字减少的速度是很快的，因此只要每次寻找一下比当前取完模之后的数小的数就可以了。用线段树寻找一下。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-6; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-'0'; c=getchar();} } const int maxn=100010; int T,n,Q,a[maxn],s[4*maxn],res,pos; void build(int l,int r,int rt) { if(l==r) { s[rt]=a[l];return; } int m=(l+r)/2; build(l,m,2*rt); build(m+1,r,2*rt+1); s[rt]=min(s[2*rt],s[2*rt+1]); } void force(int l,int r,int rt,int num) { if(l==r) { pos=l; res=a[l]; return; } int m=(l+r)/2; if(s[2*rt]<=num) force(l,m,2*rt,num); if(res!=-1) return; else force(m+1,r,2*rt+1,num); if(res!=-1) return; } void get(int L,int R,int num,int l,int r,int rt) { if(L<=l&&r<=R) { if(s[rt]>num) return; force(l,r,rt,num); return; } int m=(l+r)/2; if(L<=m) get(L,R,num,l,m,2*rt); if(res!=-1) return; if(R>m) get(L,R,num,m+1,r,2*rt+1); if(res!=-1) return; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); scanf("%d",&Q); for(int i=1;i<=Q;i++) { int L,R; scanf("%d%d",&L,&R); int ans=a[L]; pos=L; while(1) { if(ans==0||pos==R) break; res=-1; get(pos+1,R,ans,1,n,1); if(res==-1) break; ans=ans%res; } printf("%d ",ans); } } return 0; }