Luogu2714 四元组统计

发表于 分类于 ， ， 阅读次数：

题意：给出 个正整数 ，统计有多少个四元组 满足 ，。

多组数据，，，时限 。

记 为 中 的出现次数。

记 ， 即为 的倍数的出现次数和。

记 ，即 是 的倍数的四元组的个数（等价于要求四个数都是 的倍数）。

计算 ， 即为答案。

注：用“反演动机”也能完成推理，上面给出的是一种较为传统的组合意义方法，多见于早期题解中。

复杂度 或 。

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
#include <algorithm>
#include <cstdio>

using ll = long long;
const int MaxN = 1e4+5;

void Rsum(ll *f, int n) {
    for (int x=1; x<=n; x++)
        for (int y=2; x*y<=n; y++)
            f[x] += f[x*y];
}
void Rdif(ll *f, int n) {
    for (int x=n; x; x--)
        for (int y=2; x*y<=n; y++)
            f[x] -= f[x*y];
}

ll F[MaxN];

void solve() {
    int M, N = 0;
    if (scanf("%d", &M)==EOF)
        exit(0);
    for (int i=1; i<=M; i++) {
        int x;
        scanf("%d", &x);
        F[x]++;
        N = std::max(N, x);
    }
    
    Rsum(F, N);
    for(int i=1; i<=N; i++)
        F[i] = (F[i]-3)*(F[i]-2)*(F[i]-1)*F[i]/24;
    Rdif(F, N);
    
    printf("%lld\n",F[1]);
    
    for(int i=1; i<=N; i++)
        F[i] = 0;
}

int main() {
    while(true) solve();
    return 0;
}