CF1553F Pairwise Modulo 题解

题目链接：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)\)

代码：

#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;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/AlexWei/solution-cf1553f

[2] https://www.luogu.com.cn/blog/zankizero/solution-cf1553f