题解 CF1553F 【Pairwise Modulo】

meyi · 2021-07-25 12:01:53 · 题解

赛时没看到 a_i 互不相同，傻乎乎地写了个根号分治还没调出来，补一个好写的双 \log 做法。

不难发现 p_i=p_{i-1}+\sum\limits_{j=1}^{i-1}(a_j\bmod a_i)+\sum\limits_{j=1}^{i-1}(a_i\bmod a_j)

上面的式子的第一部分可以递推，考虑如何处理后面两个部分。

为了方便，这里设 \max\{a_i\}=m

第二部分的处理：

总和先加上 \sum\limits_{j=1}^{i-1}a_j，对于所有 ka_i\le m 的非负整数 k，查询 [ka_i,(k+1)a_i) 内的数的个数 x，总和减去 xka_i。

这是因为，若 a_j 在 [ka_i,(k+1)a_i) 内，则 a_j \bmod a_i = a_j-ka_i。

第三部分的处理：

开一个数组 b，对于所有 ka_i\le m 的正整数 k，给 b_{ka_i} 加上 a_i，然后总和加上 ia_i-\sum\limits_{j=1}^{a_i}b_j。

这是因为，a_i \bmod a_j=a_i-\lfloor \frac{a_i}{a_j}\rfloor a_j。

我们需要一个支持单点加和查询前缀和的数据结构，树状数组可以很好地满足需求。

于是我们以 O(n\ln m \log m) 的复杂度解决了本题。

实现细节见代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=3e5+10,mx=3e5;
#define lowbit(k) ((k)&(-k))
template<typename T>
struct BIT{
    T c[maxn];
    int mx_idx;
    inline void clear(){memset(c,0,sizeof(T)*(mx_idx+1));}
    inline void add(int k,T v){
        for(;k<=mx_idx;k+=lowbit(k))c[k]+=v;
    }
    inline T query(int k){
        T ret=0;
        for(;k;k^=lowbit(k))ret+=c[k];
        return ret;
    }
    inline T query(int l,int r){
        return query(r)-query(l-1);
    }
};
BIT<int>c1;
BIT<ll>c2;
int a[maxn],n;
ll ans,pre;
int main(){
    scanf("%d",&n);
    c1.mx_idx=c2.mx_idx=mx;
    for(ri i=1;i<=n;++i){
        scanf("%d",a+i);
        ans+=pre;
        pre+=a[i];
        for(ri j=a[i];j<=mx;j+=a[i])ans-=1ll*c1.query(j,min(j+a[i]-1,mx))*j;
        c1.add(a[i],1);
        ans+=1ll*(i-1)*a[i]-c2.query(a[i]);
        for(ri j=a[i];j<=mx;j+=a[i])c2.add(j,a[i]);
        printf("%lld ",ans);
    }
    return 0;
}