这题可以求(val)为每一种(i)的(f(l,r))数量,答案就是(sum_{i=1}^{max a} i*(val_{f(l,r)}= i)的数量()),然后可以通过差分,改为(val_{f(l,r)}le i)数量减(val_{f(l,r)}le i-1)的数量.另外可以发现如果固定左端点(l),然后右端点(r)向右移动,那么所得到的(val_{f(l,r)})一定是单调不增的,所以可以从小到大枚举(i),然后对每个左端点维护一个值,表示要满足(val_{f(l,r)}le i),右端点最小是多少
如果把(val_{f(l,r)}le i)改为(val_{f(l,r)}le i-1),那么也就是右端点要移到区间内不超过两个数满足(gcd)为(i),放宽条件,可以看成要满足区间内不超过两个数为(i)的倍数,所以把权值为(i)的倍数的所有位置提出来,分别记为(ps_1,ps_2,ps_3...ps_m)
-
然后如果区间左端点(l>ps_2),那么这样的区间右端点在哪都不合法,我们可以把这样的左端点的右端点全改为(n+1);
-
如果(ps_1<lle ps_2),那么要满足右端点右边没有是(i)的倍数的数,所以右端点应该在(ps_m)及以后,就把这些右端点和(ps_m)取(max);
-
如果(lle ps_1),那么要满足右端点右边最多有一个是(i)的倍数的数,所以右端点应该在(ps_{m-1})及以后
然后就可以区间取(max)实现上述操作,可以知道(val_{f(l,r)}le i)的数量就是(sum_{i=1}^{n}n-r_i+1).实现时因为(r_i)是单调不增的,那么可以加一些剪枝,如果修改区间最小值(le)当前修改值就直接退出,如果最大值(<)修改值就区间赋值,那么可以做到(O(nlogn)).还要注意(i)的倍数的位置集合的预处理,只有前两项和后两项是有用的,所以其他的可以不加入贡献
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
const int N=2e5+10;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m;
LL ans,nm[N],c1,c2;
vector<int> a[N],ps[N];
#define mid ((l+r)>>1)
LL s[N<<2];
int ma[N<<2],mi[N<<2],tg[N<<2];
void psup(int o)
{
s[o]=s[o<<1]+s[o<<1|1];
ma[o]=max(ma[o<<1],ma[o<<1|1]);
mi[o]=min(mi[o<<1],mi[o<<1|1]);
}
void cv(int o,int l,int r,int x)
{
s[o]=1ll*(r-l+1)*x;
ma[o]=mi[o]=x;
tg[o]=x;
}
void psdn(int o,int l,int r)
{
if(tg[o])
cv(o<<1,l,mid,tg[o]),cv(o<<1|1,mid+1,r,tg[o]),tg[o]=0;
}
void modif(int o,int l,int r,int ll,int rr,int x)
{
if(mi[o]>=x) return;
if(ll<=l&&r<=rr&&ma[o]<x){cv(o,l,r,x);return;}
psdn(o,l,r);
if(ll<=mid) modif(o<<1,l,mid,ll,rr,x);
if(rr>mid) modif(o<<1|1,mid+1,r,ll,rr,x);
psup(o);
}
void bui(int o,int l,int r)
{
if(l==r){s[o]=ma[o]=mi[o]=l;return;}
bui(o<<1,l,mid),bui(o<<1|1,mid+1,r);
psup(o);
}
int main()
{
n=rd();
for(int i=1;i<=n;++i)
{
int x=rd();
m=max(m,x);
a[x].push_back(i);
}
for(int i=1;i<=m;++i)
{
for(int j=1;i*j<=m;++j)
{
int nn=a[i*j].size();
if(nn<=4)
for(int k=0;k<nn;++k)
ps[i].push_back(a[i*j][k]);
else
{
ps[i].push_back(a[i*j][0]);
ps[i].push_back(a[i*j][1]);
ps[i].push_back(a[i*j][nn-2]);
ps[i].push_back(a[i*j][nn-1]);
}
}
}
bui(1,1,n);
for(int i=m;~i;--i)
{
nm[i]=1ll*(n+1)*n-s[1];
int nn=ps[i].size();
if(nn<=1) continue;
sort(ps[i].begin(),ps[i].end());
modif(1,1,n,1,ps[i][0],ps[i][nn-2]);
modif(1,1,n,ps[i][0]+1,ps[i][1],ps[i][nn-1]);
if(ps[i][1]<n) modif(1,1,n,ps[i][1]+1,n,n+1);
}
for(int i=1;i<=m;++i) ans+=1ll*i*(nm[i]-nm[i-1]);
printf("%lld
",ans);
return 0;
}