CF1553F Pairwise Modulo 题解

题意：

给定一个由不同数组成的序列 $a$ ，定义 $p_k$ 为：
$p_k = \sum_{i=1}^k \sum_{j=1}^k a_i \bmod a_j$
其中 $a_i \bmod a_j$ 表示 $a_i$ 除以 $a_j$ 的余数。对于每个 $i \in [1,n]$ ，求出 $p_i$ 。

数据范围：

$2 \le n \le 2 \times 10^5,~1 \le a_i \le 3\times 10^5$ 。

先来推推式子：

$\begin{aligned} p_{k+1} &= \sum_{i=1}^{k + 1} \sum_{j=1}^{k + 1} a_i \bmod a_j \\[3pt]&= \sum_{i=1}^{k} \sum_{j=1}^{k + 1} a_i \bmod a_j + \sum_{j=1}^{k + 1} a_{k+1} \bmod a_j \\[3pt]&=\sum_{i=1}^k \sum_{j=1}^k a_i \bmod a_j +\sum_{i=1}^{k} a_i\bmod a_{k+1}+\sum_{j=1}^{k + 1} a_{k+1} \bmod a_j \\[3pt]&= p_k +\sum_{i=1}^{k} a_i\bmod a_{k+1}+\sum_{j=1}^{k + 1} a_{k+1} \bmod a_j \end{aligned}$

方便起见，我们记 $M=\max a_i$

考虑用树状数组维护第三部分。不过在此之前，我们可以先尝试用树状数组维护第二部分。

首先总和先加上 $\sum_{j=1}^{i-1} a_j$ ，接着对于所有 $ca_i \le M$ ，查询 $\left[ca_i,(c+1) a_i\right)$ 内的数的个数 $c$

然后总和减去 $xca_i$ 。这是因为，如果 $a_j$ 在 $\left[ca_i,(c+1) a_i\right)$ 内，则 $a_j \bmod a_i = a_j - ca_i$ 。

类似地，考虑如何维护第三部分。定义数组 $b$ ，对于所有 $ca_i\le M$ 的正整数 $c$ ，给 $b_{ca_i}$ 加上 $a_i$

然后总和加上 $ia_i - \sum _{ j = 1} ^ {a_i} b_j$ 。这是因为 $a_i \bmod a_j=a_i-\left\lfloor a_i / a_j\right\rfloor\times a_j$ 。

因为 $a_i$ 互不相同，所以我们枚举的区间总数为 $\mathcal{O}(\sum \frac{M}{a_i})\approx\mathcal{O}(M\ln M)$ ，参考调和级数。

因此时间复杂度 $\mathcal{O}(n\log^2 n)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))
const int M = 3e5 + 5;

struct BIT
{
    int tree[N];
    #define lowbit(x) ((x) & (-(x)))
    void add(int x,int v) {
        for(int i = x; i && i <= M; i += lowbit(i)) tree[i] += v;
    }
    int sum(int x) {
        int res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res;
    }
    int sum(int l,int r) { return sum(r) - sum(l - 1); }
} c1,c2;
int n,res,pre,a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i]; res += pre; pre += a[i];
        for(int j = a[i]; j <= M; j += a[i]) {
            res -= j * c1.sum(j, min(j + a[i] - 1, M));
        } c1.add(a[i], 1);
        res += (i - 1) * a[i] - c2.sum(a[i]);
        for(int j = a[i]; j <= M; j += a[i]) c2.add(j, a[i]);
        cout << res << " \n"[i == n];
    }
    return 0;
}