题意定义f(l,r)为去掉[l,r]部分后剩下的数任意两个数的最大公约数的最大值
现在求f(l,r)的和
由于每个数ai最大只有200000，因此我们穷举因子x，记录以其为因子的a[i]的i值并按i升序。
下面我们从大到小穷举每个因子x，我们依次计算以f(l,r)=x的区间数，
有了上述的维护信息，我们很容易三种情况的区间满足f(l,r)=x（我就不具体细说了）
令pre[i]表示当前以第i个位置结尾的区间满足任意j(1<=j<=pre[i])，f(j,i)<x
显然f(l,r)=x的区间数=当前还没计算过的区间数-∑pre[i]
这就要维护∑pre[i]，每次修改是将一段区间pre[i]>x的数赋值为x
显然pre[i]是单调不上升，因此可以用线段树维护之
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
int laz[*],mi[*],mx[*];
ll tr[*];
vector<int> g[];
int n,m;
void build(int i,int l,int r)
{
laz[i]=-;
if (l==r) mx[i]=mi[i]=tr[i]=l;
else {
int m=(l+r)>>;
build(i*,l,m);
build(i*+,m+,r);
tr[i]=tr[i*]+tr[i*+];
mx[i]=max(mx[i*],mx[i*+]);
mi[i]=min(mi[i*],mi[i*+]);
}
} void work(int i,int l,int r,int x,int y,int z)
{
// if (i==1) cout <<z<<endl;
if (x>y) return;
if (mx[i]<=z) return;
if (x<=l&&y>=r&&mi[i]>z)
{
mi[i]=mx[i]=laz[i]=z;
tr[i]=(ll)(r-l+)*z;
}
else {
int m=(l+r)>>;
if (laz[i]>-)
{
laz[i*]=laz[i*+]=laz[i];
mi[i*]=mx[i*]=laz[i];
mi[i*+]=mx[i*+]=laz[i];
tr[i*]=(ll)laz[i]*(m-l+);
tr[i*+]=(ll)laz[i]*(r-m);
laz[i]=-;
}
if (x<=m) work(i*,l,m,x,y,z);
if (y>m) work(i*+,m+,r,x,y,z);
tr[i]=tr[i*]+tr[i*+];
mx[i]=max(mx[i*],mx[i*+]);
mi[i]=min(mi[i*],mi[i*+]);
}
} int main()
{
scanf("%d",&n);
for (int i=; i<=n; i++)
{
int x;scanf("%d",&x);
for (int j=; j*j<=x; j++)
if (x%j==)
{
g[x/j].push_back(i);
if (j*j!=x) g[j].push_back(i);
}
m=max(m,x);
}
build(,,n);
ll pre=(ll)n*(n+)/;
ll ans=;
for (int i=m; i; i--)
{
if (g[i].size()<) continue;
int j=g[i].size()-;
work(,,n,g[i][]+,g[i][j]-,g[i][]);
work(,,n,,g[i][j-]-,);
work(,,n,g[i][]+,n,g[i][]);
ans+=(pre-tr[])*(ll)i;
// cout <<tr[1]<<endl;
pre=tr[];
}
printf("%lld\n",ans);
}