赛时并没有能调出来:(
这是一个 \(O(n\sqrt{n}\log n)\) 的屑做法，主要原因是我看到了 \(a_i\) 互不相等，但根本没想到怎么去用。
设 \(maxn=\max\limits_{i=1}^{n}a_i\)，\(len=\sqrt{maxn}\) 下文将用到。
考虑对每个 \(a_i\) 算贡献，有 \(2\) 种：
-
第 \(1\) 种是作为被模数。
如果模数比 \(a_i\) 大，很明显余数为 \(a_i\)，于是我们就只需要求模数比 \(a_i\) 小的。
对于 \(a_i\)，我们再分 \(2\) 种情况讨论:
-
第一种是模数 \(x\) 小于等于 \(len\)，对于这部分，我们发现一个只有不超过 \(len\) 个数，所以暴力处理。
-
第二种是模数 \(x\) 大于 \(len\)，对于这部分，我们发现 \(\left\lfloor\dfrac{a_i}{x}\right\rfloor\) 小于 \(len\)，只有不超过 \(len\) 个数，所以我们枚举 \(\left\lfloor\dfrac{a_i}{x}\right\rfloor\)，求出 \(x\) 的上下界，答案为 \(a_i·cnt-\sum\limits x\)，\(cnt\) 为满足条件的 \(x\) 的个数。
-
-
第 \(2\) 种是作为模数。
对于 \(a_i\)，我们依旧是分两种讨论：
-
如果 \(a_i\)? 小于等于 \(len\)?，我们发现这样的 \(a_i\)? 值域范围只有 \(len\)? 个。于是，每个新加入的数，对于任意的 \(j(j\leq len)\)? 求出余数，预处理出 \(sum_{i,j}\)? 表示模 \(i\)? 余 \(j\)? 的数的个数；
-
如果 \(a_i\)? 大于 \(len\)?，我们发现，它将整个值域范围分成了不超过 \(len\)? 段，也就是说对于任意的被模数 \(x\)?，都有 \(\left\lfloor\dfrac{x}{a_i}\right\rfloor\leq len\)?，那就枚举 \(\left\lfloor\dfrac{x}{a_i}\right\rfloor\)? 求出 \(x\)? 的上下界，答案为 \(\sum x-cnt·a_i\)??，其中 \(cnt\) 表示满足条件的 \(x\) 的个数，这两部分都可以用树状数组维护。
-
代码：
#include<bits/stdc++.h>
#define LL long long
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define DF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=3e5+10,M=610;
int n,a[N],maxn;
LL sum[M][M],ans,l[N];
struct BIT{
LL t[N];
void add(int x,LL y){for(;x<=maxn;x+=x&-x)t[x]+=y;}
LL query(int x){if(x<0)return 0ll;LL ans=0;for(;x;x-=x&-x)ans+=t[x];return ans;}
}T1,T2;
signed main(){
cin>>n;
F(i,1,n){
cin>>a[i];
maxn=max(maxn,a[i]);
}int len=sqrt(maxn);
F(i,1,n){
ans+=a[i]*(i-1-T2.query(a[i]));
F(j,1,len){
if(j>=a[i])break;
ans+=l[j]*(a[i]%j);
}
F(j,1,len){
int l=max(len+1,a[i]/(j+1)+1),r=a[i]/j;
if(r<=len)break;
ans+=(T2.query(r)-T2.query(l-1))*a[i]-(T1.query(r)-T1.query(l-1))*j;
}
if(a[i]<=len){
F(j,1,a[i]-1)
ans+=sum[a[i]][j];
}else{
for(int j=0;j<=maxn;j+=a[i])
ans+=T1.query(min(maxn,j+a[i]-1))-T1.query(j-1)-(T2.query(min(maxn,j+a[i]-1))-T2.query(j-1))*j;
}
F(j,2,len){
int k=a[i]%j;
if(!k)continue;
sum[j][k]+=k;
}
T1.add(a[i],a[i]);T2.add(a[i],1);
l[a[i]]++;
yout<<ans<<" ";
}
return 0;
}