题意我就不说了
解析: 莫队,先预处理出以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=;
typedef __int64 LL;
int N,M,A[maxn],block;
struct Ques
{
int x,y,id;
Ques(int x=,int y=,int id=):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==?a:gcd(b,a%b); }
struct node
{
int id,g;
node(int id=,int g=):id(id),g(g){}
};
vector<node> vl[maxn],vr[maxn];
void GetLe()
{
for(int i=;i<=N;i++) //得到以i为右端点连续区间的gcd值
{
if(i==){ vl[i].push_back(node(i,A[i])); continue; }
int g=A[i],id=i;
int Size=vl[i-].size();
for(int j=;j<Size;j++)
{
node& t=vl[i-][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>=;i--)
{
if(i==N){ vr[i].push_back(node(i,A[i])); continue; }
int g=A[i],id=i;
int Size=vr[i+].size();
for(int j=;j<Size;j++)
{
node& t=vr[i+][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=;
for(int i=;i<Size;i++)
{
node& t=vl[y][i];
if(t.id>=x)
{
ret+=(LL)t.g*(ny-t.id+);
ny=t.id-; //跳过去
}
else{ ret+=(LL)t.g*(ny-x+); break; }
}
return ret;
}
LL WorkRi(int x,int y)
{
int nx=x;
LL ret=;
int Size=vr[x].size();
for(int i=;i<Size;i++)
{
node& t=vr[x][i];
if(t.id<=y)
{
ret+=(LL)t.g*(t.id-nx+);
nx=t.id+;
}
else { ret+=(LL)t.g*(y-nx+); break; }
}
return ret;
}
LL ans[maxn];
void solve()
{
for(int i=;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=,y=;
LL ret=;
for(int i=;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=;i<M;i++) printf("%lld\n",ans[i]); //输出
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(int i=;i<=N;i++) scanf("%d",&A[i]);//输入
scanf("%d",&M);
int x,y;
for(int i=;i<M;i++)
{
scanf("%d%d",&x,&y);
ques[i]=Ques(x,y,i); //离线保存查询
}
solve();
}
return ;
}