POJ 3904 - Sky Code

发表于 更新于 分类于 阅读次数：

给出一个序列 \(a_n\) , 求选出四个数并且四个数的最大公约数为1的情况数，根据莫比乌斯反演定理

\[ \begin{aligned} & \sum_{u,v,p,q \in \{a_n\} } [{\rm gcd}(a_u, a_v, a_p, a_q) = 1]  \\ = & \sum_{u,v,p,q \in \{a_n\}}  \sum_{t | d} \mu (t) \end{aligned} \]

其中 \(d = {\rm gcd}(a_u, a_v, a_p, a_q)\)，则调换求和次序，上式可化为

\[\sum_{t = 1}^{\max \{ a_n\} } \mu (t) {f(t) \choose 4}\]

其中 \(f(t)\) 为 \(\{a_n\}\) 中 \(t\) 的倍数的个数，求法类似埃筛。那么预处理出莫比乌斯函数的函数值，就可以在 \(O(k \log k)\) 的时间得到答案，其中 $k = { a_n } $。

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
51
52
53
54
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAX_N = 10000 + 5;
int n, a[MAX_N], h[MAX_N];

namespace LinearSieve {
    bool vis[MAX_N];
    int mu[MAX_N], p[MAX_N], tot;
    void run() {
        mu[1] = 1;
        vis[0] = vis[1] = 1;
        for (int i = 2; i < MAX_N; ++i) {
            if (!vis[i]) {
                p[++tot] = i;
                mu[i] = -1;
            }
            for (int j = 1; j <= tot && LL(i) * p[j] < MAX_N; ++j) {
                vis[i * p[j]] = 1;
                if (i % p[j] == 0) break;
                else mu[i * p[j]] -= mu[i];
            }
        }
    }
};

LL getComb(LL x) {
    if (x < 4) return 0;
    return x * (x - 1) * (x - 2) * (x - 3) / 24;
}

int main() {
    LinearSieve::run();
    while (scanf("%d", &n) != EOF) {
        memset(h, 0, sizeof h);
        int maxNum = -1;
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), ++h[a[i]], maxNum = max(maxNum, a[i]);
        LL ans = 0;
        for (int t = 1; t <= maxNum; ++t) {
            LL sum = 0;
            for (int u = t; u <= maxNum; u += t) {
                sum += h[u];
            }
            ans += LinearSieve::mu[t] * getComb(sum);
        }
        printf("%lld\n", ans);
    }
    return 0;
}