The sum of gcd
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
You have an array A,the length of A is n
Let f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)
Let f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
First line has one integers n
Second line has n integers Ai
Third line has one integers Q,the number of questions
Next there are Q lines,each line has two integers l,r
1≤T≤3
1≤n,Q≤104
1≤ai≤109
1≤l<r≤n
First line has one integers n
Second line has n integers Ai
Third line has one integers Q,the number of questions
Next there are Q lines,each line has two integers l,r
1≤T≤3
1≤n,Q≤104
1≤ai≤109
1≤l<r≤n
Output
For each question,you need to print f(l,r)
Sample Input
2
5
1 2 3 4 5
3
1 3
2 3
1 4
4
4 2 6 9
3
1 3
2 4
2 3
5
1 2 3 4 5
3
1 3
2 3
1 4
4
4 2 6 9
3
1 3
2 4
2 3
Sample Output
9
6
16
18
23
10
6
16
18
23
10
Author
SXYZ
Source
题意：一句话题意；
思路：首先莫队离线处理，式必须的；
然后重点就在于如何更新那个变化的值；
根据取模的性质，每次取模最少/2；
gcd也是同理；
也就是说区间的gcd不同数的个数最多不超过log（n）个；
这样就可以更新了；
开始我写了一个RMQ，每次二分查找每一段，超时了；
然后学到一个预处理的姿势；
预处理见代码init那段；
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x) cout<<"bug"<<x<<endl;
const int N=1e4+,M=4e6+,inf=;
const ll INF=1e18+,mod=1e9+; /// 数组大小 int a[N];
int n,pos[N],k;
vector<pair<int,int> >l[N],r[N];
struct is
{
int l,r,now;
bool operator <(const is &b)const
{
if(pos[l]!=pos[b.l])
return pos[l]<pos[b.l];
return r<b.r;
}
}p[N];
ll out[N],ans;
void prex(int L,int R,int flag)
{
ll sum=;
int p=L;
for(int i=;i<l[L].size();i++)
{
int k=min(R,l[L][i].first);
if(k>=p)
sum+=1LL*(k-p+)*l[L][i].second;
if(k>=R)break;
p=k+;
}
if(flag==)ans+=sum;
else ans-=sum;
} void nexx(int L,int R,int flag)
{
ll sum=;
int p=R;
for(int i=;i<r[R].size();i++)
{
int k=max(r[R][i].first,L);
if(p>=k)
sum+=1LL*(p-k+)*r[R][i].second;
if(k<=L)break;
p=k-;
}
if(flag==)ans+=sum;
else ans-=sum;
}
void init()
{
for(int i=;i<=n;i++)
l[i].clear(),r[i].clear();
ans=;
// 预处理l
l[n].push_back(make_pair(n,a[n]));
for(int i=n-;i>=;i--)
{
int g=a[i];
int p=i;
for(int j=;j<l[i+].size();j++)
{
int k=__gcd(g,l[i+][j].second);
if(g!=k)l[i].push_back(make_pair(p,g));
g=k;
p=l[i+][j].first;
}
l[i].push_back(make_pair(p,g));
}
//预处理r
r[].push_back(make_pair(,a[]));
for(int i=;i<=n;i++)
{
int g=a[i];
int p=i;
for(int j=;j<r[i-].size();j++)
{
int k=__gcd(g,r[i-][j].second);
if(g!=k)r[i].push_back(make_pair(p,g));
g=k;
p=r[i-][j].first;
}
r[i].push_back(make_pair(p,g));
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
k=sqrt(n);
for(int i=; i<=n; i++)
scanf("%d",&a[i]),pos[i]=(i-)/k+;
init();
int q;
scanf("%d",&q);
for(int i=; i<=q; i++)
scanf("%d%d",&p[i].l,&p[i].r),p[i].now=i;
sort(p+,p++q);
int L=,R=;
for(int i=; i<=q; i++)
{
while(L<p[i].l)
{
prex(L,R,);
L++;
}
while(L>p[i].l)
{
L--;
prex(L,R,);
}
while(R>p[i].r)
{
nexx(L,R,);
R--;
}
while(R<p[i].r)
{
R++;
nexx(L,R,);
}
out[p[i].now]=ans;
}
for(int i=; i<=q; i++)
printf("%lld\n",out[i]);
}
return ;
}