题解：CF1884D Counting Rhyme

· · 题解

题意

给定长度为 n 的数组 a_1,\dots,a_n（1\le a_i\le n）。
我们称一对下标 (i,j)（i<j）是好的，当且仅当不存在数组中的某个元素 a_k，使得 a_k 同时整除 a_i 和 a_j，求好对的数量。

思路

易知，若 (i,j) 是一个好对，当且仅当不存在一个 a_k 使得 a_k\mid \gcd(a_i, a_j)。

不妨设

0 & \exists i\in[1, n],a_i\mid x\\ 1 & \text{otherwise} \end{cases}.

那么题目所求就可以转化为

\sum\limits_{i = 1}^n\sum\limits_{j = i + 1} ^ nf(\gcd(a_i,a_j)).

考虑枚举最大公因数：

\sum\limits_{d = 1}^n\sum\limits_{i = 1}^n\sum\limits_{j = i + 1} ^ nf(d)[\gcd(a_i,a_j) = d].

把 f(d) 提出来，得：

\sum\limits_{d = 1}^nf(d)\sum\limits_{i = 1}^n\sum\limits_{j = i + 1} ^ n[\gcd(a_i,a_j) = d].

易发现答案可以在调和级数 O(n\ln n) 内算出来。

::::success[Code]

#include <bits/stdc++.h>

#define inl inline
#define ls (p << 1)
#define rs (p << 1 | 1)
#define Cst constexpr
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define pb(x) push_back(x)
#define ppc(x) __builtin_popcount(x)
#define mems(x, v) memset((x), (v), sizeof(x))
#define memc(x, y) memcpy((x), (y), sizeof(x))
#define All(x) (x).begin(), (x).end()

using LL = long long;
using ULL = unsigned long long;
using namespace std;

Cst int N = 1e6 + 5;
auto FIO = []() {
    return cin.tie(0)->sync_with_stdio(0), 0;
}();
int n, a[N], cnt[N], tot[N]; LL f[N];
bitset<N> g;
void Solve() {
    cin >> n; 
    for (int i = 1; i <= n; ++i) cnt[i] = f[i] = tot[i] = 0, g[i] = 1;
    for (int i = 1; i <= n; ++i) 
        cin >> a[i], ++cnt[a[i]];
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            tot[i] += cnt[j];
            if (cnt[i]) g[j] = 0;
        }
    }   
    LL res = 0;
    for (int i = n; i >= 1; --i) {
        f[i] = (LL)tot[i] * (tot[i] - 1) / 2;
        for (int j = i << 1; j <= n; j += i) f[i] -= f[j];
        res += f[i] * g[i];
    }
    cout << res << '\n';
}
int main() {
    int T; cin >> T;
    while (T--) Solve();
}

::::