离线+分块！！
思路：序列a[1],a[2],a[3]……a[n]
num[i]表示区间[L,R]中是i的倍数的个数；euler[i]表示i的欧拉函数值。
则区间的GCD之和sum=∑(C(num[i],2)*euler[i]).当增加一个数时，若有约数j，则只需加上num[j]*euler[j]，之后再num[j]++;
反之亦然！！
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 20002
using namespace std;
int R,L,an[MAX],euler[MAX],ans[MAX],res,num[MAX];
bool vis[MAX],prime[MAX];
struct node
{
int x,y,l,p;
}q[MAX];
vector<int>p[MAX];
void init()//初始化欧拉函数值
{
int i,j;
for(i=;i<MAX;i++) euler[i]=i;
for(i=;i<MAX;i++)
if(euler[i]==i){
for(j=i;j<MAX;j+=i)
euler[j]=euler[j]/i*(i-);
}
}
void factor(int n)//分解因子
{
p[n].clear();
for(int i=;i*i<=n;i++){
if(n%i==){
p[n].push_back(i);
if(i*i!=n) p[n].push_back(n/i);
}
}
}
bool cmp(const node &a,const node &b)
{
if(a.l==b.l) return a.y<b.y;
return a.l<b.l;
}
void query(int x,int y,int flag)//查询操作
{
int t;
if(flag){
for(int i=x;i<L;i++){
for(int j=;j<p[an[i]].size();j++){
t=p[an[i]][j];
res+=num[t]*euler[t];
num[t]++;
}
}
for(int i=L;i<x;i++){
for(int j=;j<p[an[i]].size();j++){
t=p[an[i]][j];
num[t]--;
res-=num[t]*euler[t];
}
}
for(int i=y+;i<=R;i++){
for(int j=;j<p[an[i]].size();j++){
t=p[an[i]][j];
num[t]--;
res-=num[t]*euler[t];
}
}
for(int i=R+;i<=y;i++){
for(int j=;j<p[an[i]].size();j++){
t=p[an[i]][j];
res+=num[t]*euler[t];
num[t]++;
}
}
}
else{
for(int i=x;i<=y;i++){
for(int j=;j<p[an[i]].size();j++){
t=p[an[i]][j];
res+=num[t]*euler[t];
num[t]++;
}
}
}
L=x;R=y;
}
int main(){
int n,t,i,j,m,c,ca=;
init();
for(i=;i<=;i++) factor(i);
scanf("%d",&c);
while(c--){
scanf("%d",&n);
for(i=;i<=n;i++) scanf("%d",&an[i]);
m=sqrt(1.0*n);
scanf("%d",&t);
for(i=;i<t;i++){
scanf("%d%d",&q[i].x,&q[i].y);
q[i].l=q[i].x/m;
q[i].p=i;
}
sort(q,q+t,cmp);
res=;
memset(num,,sizeof(num));
for(i=;i<t;i++){
query(q[i].x,q[i].y,i);
ans[q[i].p]=res;
}
printf("Case #%d:\n",++ca);
for(i=;i<t;i++)
printf("%d\n",ans[i]);
}
return ;
}