这是第一场ccpc预赛的题目，链接：https://acm.hdu.edu.cn/showproblem.php?pid=7107

好久好久终于补上这个通天坑了

题目思路是，从大到小枚举每一个gcd，为了方便我们设这个数字为d，则所选区间内必然有两个d的倍数。那我们先把d的倍数所在下标先列举出来，如最后枚举出的下标是这样的[3,5,7,10]，在不考虑其他数字干扰的情况下，如0<l<=3时，r只能不小于5。3<l<=5时，r只能不小于7。以此类推

这是无干扰情况，如果是有干扰呢？

那我们考虑用数组mx来保存每一l所能取到r的最大值是多少。很显然mx_l是递增的（确实是递增的但我不会证明XD）。对于d倍数所在下标，我们设这个集合为g，对于每一个g_i，求l∈(g_i-1,gi]且mx_l≥g_i+1的最小l，然后将[l,g_i]区间内所有mx全更新为g_i+1-1，然后最后统计答案加上两次总mx之差即可即可

#include <bits/stdc++.h>
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int MAX=1e5+5;
ll n,loc[MAX],mx[MAX<<2],sum[MAX<<2],lzy[MAX<<2];
void push_up(ll rt){
	mx[rt]=max(mx[lson],mx[rson]);
	sum[rt]=sum[lson]+sum[rson];
}
void push_down(ll rt,ll l,ll r){
	if(!lzy[rt]) return;
	ll mid=(l+r)>>1;
	lzy[lson]=lzy[rson]=lzy[rt];
	mx[lson]=mx[rson]=lzy[rt];
	sum[lson]=(mid-l+1)*lzy[rt];
	sum[rson]=(r-mid)*lzy[rt];
	lzy[rt]=0;
}
void build(ll rt,ll l,ll r){
	if(l==r){
		mx[rt]=n,sum[rt]=n,lzy[rt]=0;
		return;
	}
	lzy[rt]=0;
	ll mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	push_up(rt);
}
ll find(ll rt,ll l,ll r,ll L,ll R,ll V){
	if(l==r){
		if(l>R) return -1;
		return max(l,L);
	}
	push_down(rt,l,r);
	ll mid=(l+r)>>1;
	if(mx[lson]>V){
		return find(lson,l,mid,L,R,V);
	}
	else
	if(mx[rson]>V){
		return find(rson,mid+1,r,L,R,V);
	}
	return -1;
}
void update(ll rt,ll l,ll r,ll L,ll R,ll v){
	if(l>=L&&r<=R){
		sum[rt]=(r-l+1)*v;
		mx[rt]=v;
		lzy[rt]=v;
		return;
	}
	push_down(rt,l,r);
	ll mid=(l+r)>>1;
	if(mid>=L) update(lson,l,mid,L,R,v);
	if(mid<R) update(rson,mid+1,r,L,R,v);
	push_up(rt);
}
void solve(){
	scanf("%lld",&n);
	vector<ll>ans(n+5);
	for(int i=1;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		loc[x]=i;
	}
	build(1,1,n);
	for(int i=n;i>=1;i--){
		vector<ll>v(1);
		for(int j=i;j<=n;j+=i) v.push_back(loc[j]);
		sort(v.begin()+1,v.end());
		ans[i]=sum[1];
		for(int j=1;j+1<v.size();j++){
			int l=find(1,1,n,v[j-1]+1,v[j],v[j+1]-1);
			//cout<<l<<endl;
			if(~l){
				update(1,1,n,l,v[j],v[j+1]-1);
				//cout<<"fff";
			}
		}
		ans[i]-=sum[1];
	}
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}