分两种情况讨论
- (a_imod a_j)
- (a_i < a_j)
那么 (a_j) 对答案的贡献是 (a_i)。
- (a_i > a_j)
那么 (a_j) 对答案的贡献是 (a_i-a_j imes lfloor dfrac{a_i}{a_j} floor)，和第一个合并一下就是 (a_i imes (i-1) - lfloor dfrac{a_i}{a_j} floor)。
后面的这部分可以转化为枚举一个 (l)，在区间 ([a_j imes l,a_j imes (l+1) -1]) 上加上 (a_j imes l)，这个可以用树状数组维护。
- (a_j mod a_i)
- (a_j<a_i)
贡献为 (a_j)。
- (a_j>a_i)
贡献为 (a_j-a_i imes lfloor dfrac{a_j}{a_i} floor)，和第一种情况同理，前面一部分贡献为 (sum a_j)，后面同上一种情况，对于区间 ([a_i imes l,a_i imes (l+1) -1]) 上减去上 (a_j) 在这个区间里的个数乘上 (a_j imes l)，同样可以用树状数组维护。
时间复杂度为 (O(n log^2 n))。
#include <bits/stdc++.h>
#define reg register
#define fi first
#define se second
#define mp std::make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll rd()
{
reg ll x=0,f=0;
reg char ch=getchar();
while(!isdigit(ch)) (ch=='-')&&(f=1),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
#define int long long
const int MAXN=2e5+10;
const int MAXM=3e5+10;
int n,a[MAXN];
int c[MAXM][2];
// 0:val 1:num
void add(reg int x,reg int v,reg int op)
{
for(;x<MAXM;x+=(x&(-x))) c[x][op]+=v;
}
int qry(reg int x,reg int op)
{
reg ll ret=0;
for(;x;x-=(x&(-x))) ret+=c[x][op];
return ret;
}
void work()
{
n=rd();
for(reg int i=1;i<=n;++i) a[i]=rd();
int sum=0,ans=0;
for(reg int i=1;i<=n;++i)
{
ans+=sum+1ll*a[i]*(i-1)-qry(a[i],0);
sum+=a[i];
for(reg int j=a[i];j<MAXM;j+=a[i])
{
ans-=j*(qry(std::min(j+a[i]-1,MAXM-1),1)-qry(j-1,1));
add(j,j,0),add(std::min(j+a[i]-1,MAXM-1)+1,-j,0);
}
add(a[i],1,1);
printf("%lld ",ans);
}
puts("");
}
#undef int
int main()
{
int _=1;
// _=rd();
while(_--) work();
return 0;
}