题目描述

难度分:$1506$

输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^6)$。下标从$1$开始。

定义$f(i,j)=\lfloor \frac{max(a[i],a[j])}{min(a[i],a[j])} \rfloor$。

输出所有$f(i,j)$之和，其中$1 \leq i \lt j \leq n$。

输入样例$1$

3
3 1 4

输出样例$1$

8

输入样例$2$

6
2 7 1 8 2 8

输出样例$2$

53

输入样例$3$

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

输出样例$3$

592622

算法

整除分块

思路比较容易想到，先让数组$a$排序然后逐个将每个元素作为最小值会更好考虑。而为了使用$m+\lfloor \frac{m}{2} \rfloor+\lfloor \frac{m}{3} \rfloor+…+\lfloor \frac{m}{m} \rfloor$~$lnm$这个结论，先把$a$中的数组放入一个$vals$数组中排序去重，然后遍历$vals$按照数值去考虑，否则遍历原数组$a$一旦有大量重复的小值，这个结论就会失效，重新退化为$O(m)$的时间复杂度。

对于$vals$中的一个元素$x$，枚举倍数$t$（满足$tx \leq max_{i \in [1,n]}a[i]$）。原数组中所有在区间$[tx,(t+1)x)$里面的数除以$x$向下取整就能得到$t$，因此对答案的贡献为$counter[x] \times t \times (s[(t+1)x-1]-s[tx-1])$。其中$counter[num]$表示数值$num$在原数组中的出现次数，$s[num]$表示原数组中$\leq num$的数值有多少个。因此，还需$O(n)$预处理出$counter$，$O(m)$预处理出$s$数组，其中$m$为$a$的最大值。

但其实这里还没有做完，因为这样会使得$t=1$的情况被重复计算。$a[i]$会跟前面与自己相等的数计算贡献，也会与后面与自己相等的数计算贡献。所以遍历$a$进行去重，当遍历到$a[i]$的时候让答案减去$counter[a[i]]$，此时$counter[a[i]]$表示前缀$[1,i]$中$a[i]$的频数。这样就能去掉$a[i]$与自己，以及前面与自己相等的数进行配对所产生的贡献。

复杂度分析

时间复杂度

对数组$a$排序的时间复杂度为$O(nlog_2n)$，对其去重的时间复杂度为$O(n)$（即对$vals$排序去重）。预处理$a$值域的前缀和数组$s$的时间复杂度为$O(m)$，$m$表示$a$数组的最大值。对每个$vals$求答案，时间复杂度为$O(m+\lfloor \frac{m}{2} \rfloor+\lfloor \frac{m}{3} \rfloor+…+\lfloor \frac{m}{m} \rfloor)$，大约是$O(logm)$，因此把所有$vals[i]$算完时间复杂度为$O(nlogm)$。最后还需要遍历一遍数组$a$，对重复计算的部分去重，时间复杂度为$O(n)$。

综上，整个算法的时间复杂度为$O(n(log_2n+logm))$。

空间复杂度

$vals$的空间消耗是线性的，为$O(n)$。$a$的频数表$counter$也是线性的，为$O(n)$。前缀和数组$s$的空间复杂度与数组$a$的值域相关，为$O(m)$。因此，整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, M = 2000010;
int n, a[N], s[M];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    scanf("%d", &n);
    vector<int> vals;
    unordered_map<int, int, custom_hash> counter;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        counter[a[i]]++;
        vals.push_back(a[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    sort(a + 1, a + n + 1);
    for(int i = 0; i <= 2*a[i]; i++) {
        s[i] = 0;
    }
    for(int i = 1; i <= 2*a[n]; i++) {
        s[i] = s[i - 1] + (counter.count(i)? counter[i]: 0);
    }
    LL ans = 0;
    for(auto&[num, freq]: counter) {
        for(LL t = 1; t*num <= a[n]; t++) {
            // [t*num,(t+1)*num)中有多少个数，这些数除以num都得t
            ans += (s[(t + 1)*num - 1] - s[t*num - 1]) * t * freq;
        }
    }
    counter.clear();
    for(int i = 1; i <= n; i++) {
        counter[a[i]]++;
        ans -= counter[a[i]];
    }
    printf("%lld\n", ans);
    return 0;
}