CF1553F Pairwise Modulo

Alex_Wei · 2021-07-23 10:55:29 · 题解

题目传送门。

题意简述：给定长度为 n 的序列 a_i，对于每个 k\in [1,n]，求出 \sum_{1\leq i,j\leq k}a_i\bmod a_j。

每次考虑新加入的 a_i 对 a_j\ (1\leq j<i) 的影响，分成 a_i\bmod a_j 和 a_j\bmod a_i 来算。

• - 若 $a_j>a_i$，那么 $a_j$ 的贡献为 $a_i$。 - 若 $a_j<a_i$，那么 $a_j$ 的贡献为 $a_i-a_j\times \lfloor\dfrac{a_i}{a_j}\rfloor$。注意到前者与第一种情况的和为 $a_i\times (i-1)$，而后面一部分可以在计算 $a_j$ 时枚举 $c$，对于每个 $[c\times a_j,(c+1)\times a_j-1]$ 区间加 $c\times a_j$ 预处理出来。
• - 若 $a_j<a_i$，那么 $a_j$ 的贡献为 $a_j$。 - 若 $a_j>a_i$，那么 $a_j$ 的贡献为 $a_j-a_i\times \lfloor\dfrac{a_j}{a_i}\rfloor$。注意到前者与第一种情况的和为 $\sum a_j$，而后面一部分可以枚举 $c$，对于每个 $[c\times a_i,(c+1)\times a_i-1]$，将答案减去 $a_j$ 落在该区间的数的个数 $num\times (c\times a_i)$ 。

因为 a_i 互不相同，所以我们枚举的区间总数在 \sum\dfrac{m}{a_i}\approx m\ln m。而 区间加与单点求和 以及 单点加与区间求和 都是 BIT 的拿手好戏，因此总时间复杂度为 \mathcal{O}(n\log^2 n)。

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int N=2e5+5;
const ll M=3e5+5;

ll n,sum,res;
struct BIT{
    ll c[M];
    void add(ll x,ll v){while(x<M)c[x]+=v,x+=x&-x;}
    ll query(ll x){ll s=0; while(x)s+=c[x],x-=x&-x; return s;}
}val,num;

int main(){
    cin>>n;
    for(ll i=1,a;i<=n;i++){
        cin>>a,res+=sum+a*(i-1)-val.query(a);
        for(ll j=a;j<M;j+=a){
            int L=min(M-1,j+a-1);
            res-=j*(num.query(L)-num.query(j-1));
            val.add(j,j),val.add(L+1,-j);
        } num.add(a,1),sum+=a,cout<<res<<" ";
    }
    return 0;
}