题目描述

难度分:$2100$

输入$T(\leq 2 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^6$。

每组数据输入$n(1 \leq n \leq 10^6)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

输出有多少对$(i,j)$，满足$i \lt j$且不存在$a[k](1 \leq k \leq n)$既可以整除$a[i]$又可以整除$a[j]$。

输入样例

6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12

输出样例

0
3
26
26
124
82

算法

数论容斥

看过数论容斥这题就很简单，不然还是特别难想的。先对数组$a$求元素的频数，存入到数组$cnt$中，$cnt[i]$表示$i$在$a$中的出现次数，然后考虑一个问题，$f_k$表示满足$gcd(a_i,a_j)=k$的$(i,j)$对数量，考虑求取$f_k$。

这是个比较经典的做法，$nlnn$枚举$i \in [1,n]$所有$i$在值域$[1,n]$内的倍数。对于一个$i$，先将它倍数的频数累加起来得到$sum$，这$sum$个数中任意两个配对，都有约数$i$，一共有$C_{sum}^2$个方案。但是这$sum$个数挑两个出来有可能约数并不是$i$，而是$2i$、$3i$、…，因此要把这些去掉，则有$f_{i}=C_{sum}^{2}-f_{2i}-f_{3i}-…$。

最后我们计算答案，枚举$i \in [1,n]$，只要$cnt[i] \gt 0$，说明$i$存在于数组$a$中，以它为约数的$f$值都不能计入答案，枚举$i$的倍数$k \times i$，令$f[k \times i]=0$。这样打过标记后，最后的答案就是$\Sigma_{i \in [1,n]}f_i$。

复杂度分析

时间复杂度

计算$a$中元素的频数，以及最后计算答案遍历$\Sigma_{i \in [1,n]}f_i$，时间复杂度都是$O(n)$。而计算$f$的时候，外层遍历$i \in [1,n]$，内层在值域$[i,n]$内遍历$i$的倍数，根据调和级数公式$\frac{n}{1}+\frac{n}{2}+…+\frac{n}{n}$大概就是$lnn+C$（$C$为常数），时间复杂度为$O(nlnn)$，这也是整个算法的时间复杂度。

空间复杂度

除去输入的$a$数组，额外空间主要是$cnt$和$f$两个数组。而因为$a[i] \leq n$，这两个数组的空间都是线性的，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1000010;
int T, n, a[N], cnt[N];
LL f[N];

LL C2(LL n) {
    return n*(n - 1)/2;
}

void solve() {
    for(int i = 1; i <= n; i++) {
        cnt[a[i]]++;
    }
    for(int i = n; i >= 1; i--) {
        LL sum = 0;
        for(int j = i; j <= n; j += i) {
            sum += cnt[j];
        }
        f[i] = C2(sum);
        for(int j = i + i; j <= n; j += i) {
            f[i] -= f[j];
        }
    }
    for(int i = 1; i <= n; i++) {
        if(cnt[i] > 0) {
            for(int j = i; j <= n; j += i) {
                f[j] = 0;
            }
        }
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += f[i];
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            cnt[i] = f[i] = 0;
        }
        solve();
    }
    return 0;
}