CF1884D Counting Rhyme

发表于 更新于 本文字数： 486 阅读时长 ≈ 2 分钟

题目传送门

题目翻译：

给定长度为 nn 的序列 aa。对于 1≤i<j≤n1\leq i<j\leq n，若不存在 k∈[1,n]k\in[1,n] 使得 ak∣aia_k\mid a_i 且 ak∣aja_k\mid a_j 那么 (i,j)(i,j) 是好的。求出好的数对数量。ai,n≤106a_i,n\leq 10^6。

注意到若 ak∣aia_k\mid a_i 且 ak∣aja_k\mid a_j，那么 aka_k 一定也能整除 gcd⁡(ai,aj)\gcd(a_i,a_j)。那么我们可以通过枚举 gg，找出最大公约数为 gg 的数对的个数 fgf_g，最后答案即为 ∑fg[∀1≤k≤n,ak∤g]\sum f_g[\forall 1\leq k\leq n,a_k\nmid g]。

下面考虑计算 fgf_g。这里我们用 cntxcnt_x 表示数字 xx 在序列 aa 中出现的次数，用 sumsum 表示能被 gg 整除的数的个数。显然，sum=cntg+cnt2g+⋯+cntkg(kg≤n)sum=cnt_g+cnt_{2g}+\cdots+cnt_{kg}(kg\leq n)。由此易知，所有最大公约数能被 gg 整除的数对个数为 sum×(sum−1)2\frac{sum\times (sum-1)}{2}，接下来还需要减去最大公约数大于 gg 的情况，其实就是 f2g+f3g+⋯+fkg(kg≤n)f_{2g}+f_{3g}+\cdots+f_{kg}(kg\leq n)。即：

fg=sum×(sum−1)2−f2g−⋯−fkgf_g=\frac{sum\times (sum-1)}{2}-f_{2g}-\cdots-f_{kg}

注意到这个过程比较像埃氏筛，所以时间复杂度应该是 O(nlog⁡log⁡n)O(n\log\log n) 。但是官方题解写的是 O(nlog⁡n)O(n\log n)，我也不知道到底哪个是对的，反正能过就行了。

代码

记得开 long long 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
#define int long long
int T;
const int maxn = 1e6 + 5;
int n;
int a[maxn], cnt[maxn], vis[maxn];
int f[maxn];
void Solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        f[i] = cnt[i] = vis[i] = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cnt[a[i]]++;
    for (int i = 1; i <= n; i++)
        vis[a[i]] = 1;
    for (int i = n; i >= 1; i--)
    {
        int sum = 0;
        for (int j = i; j <= n; j += i)
        {
            sum += cnt[j];
            f[i] -= f[j];
            if (vis[i])
                vis[j] = 1;
        }
        f[i] += sum * (sum - 1) / 2;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            ans += f[i];
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        Solve();
    }
    return 0;
}