题意我就不说了
解析: 莫队，先预处理出以i为右端点的区间的gcd值，有一些连续的区间的gcd值是相同的，比如[j,i],[j+1,i],[j+2,i]的gcd值是相同的，我们可以把[j,j+2]这个
区间保存下来。同时也预处理出以i为左端点的，最后用莫队算法。详见代码实现。
代码
#include<cstdio> #include<vector> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; const int maxn=10005; typedef __int64 LL; int N,M,A[maxn],block; struct Ques { int x,y,id; Ques(int x=0,int y=0,int id=0):x(x),y(y),id(id){} bool operator < (const Ques& t) const { int a=x/block,b=t.x/block; //排序 if(a!=b) return a<b; return y<t.y; } }ques[maxn]; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } struct node { int id,g; node(int id=0,int g=0):id(id),g(g){} }; vector<node> vl[maxn],vr[maxn]; void GetLe() { for(int i=1;i<=N;i++) //得到以i为右端点连续区间的gcd值 { if(i==1){ vl[i].push_back(node(i,A[i])); continue; } int g=A[i],id=i; int Size=vl[i-1].size(); for(int j=0;j<Size;j++) { node& t=vl[i-1][j]; int ng=gcd(t.g,g); if(ng!=g) vl[i].push_back(node(id,g)); g=ng; id=t.id; } vl[i].push_back(node(id,g)); } } void GetRi() //同理 { for(int i=N;i>=1;i--) { if(i==N){ vr[i].push_back(node(i,A[i])); continue; } int g=A[i],id=i; int Size=vr[i+1].size(); for(int j=0;j<Size;j++) { node& t=vr[i+1][j]; int ng=gcd(t.g,g); if(ng!=g) vr[i].push_back(node(id,g)); g=ng; id=t.id; } vr[i].push_back(node(id,g)); } } LL WorkLe(int x,int y) { int Size=vl[y].size(); int ny=y; LL ret=0; for(int i=0;i<Size;i++) { node& t=vl[y][i]; if(t.id>=x) { ret+=(LL)t.g*(ny-t.id+1); ny=t.id-1; //跳过去 } else{ ret+=(LL)t.g*(ny-x+1); break; } } return ret; } LL WorkRi(int x,int y) { int nx=x; LL ret=0; int Size=vr[x].size(); for(int i=0;i<Size;i++) { node& t=vr[x][i]; if(t.id<=y) { ret+=(LL)t.g*(t.id-nx+1); nx=t.id+1; } else { ret+=(LL)t.g*(y-nx+1); break; } } return ret; } LL ans[maxn]; void solve() { for(int i=0;i<=N;i++) vl[i].clear(),vr[i].clear(); block=(int)sqrt(N+0.5); //分块 sort(ques,ques+M); //排序 GetLe(); //得到左边连续相同的gcd区间 GetRi(); //得到右边连续相同的gcd区间 int x=1,y=0; LL ret=0; for(int i=0;i<M;i++) //莫队的主要实现部分 { Ques& q=ques[i]; while(y<q.y){ y++; ret+=WorkLe(x,y); } while(y>q.y){ ret-=WorkLe(x,y); y--; } while(x<q.x){ ret-=WorkRi(x,y); x++; } while(x>q.x){ x--; ret+=WorkRi(x,y); } ans[q.id]=ret; //保存答案 } for(int i=0;i<M;i++) printf("%lld ",ans[i]); //输出 } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&A[i]);//输入 scanf("%d",&M); int x,y; for(int i=0;i<M;i++) { scanf("%d%d",&x,&y); ques[i]=Ques(x,y,i); //离线保存查询 } solve(); } return 0; }