题意是给出一个数组，要求三元组(a,b,c)，使得gcd(a,b,c)=1，求这些三元组的数量。数组大小和数的范围都是1到1e5。
一开始想的是基本的容斥原理，后来大佬说到可以直接套莫比乌斯反演，没想到有限域学到的莫比乌斯反演能这样用（查了一下才发现是基本NOI，ACM的模板题了，之前还没见过orz）。
学习了一下，首先先简单介绍一下莫比乌斯反演。其公式表示如下：
证明过程就简略了，主要思想就是将一个较难做的$a(n)$函数，转化成较简单的$b(n)$去求解，有限域上给的应用例子是欧拉函数相关的， ，因为直接计算欧拉函数复杂度稍高，那么就可以通过转化来计算欧拉函数。
介绍最直接的莫比乌斯反演入门题，就是给两个区间，从每个区间各取一个数，求有多少对互素的数。直接求的数量复杂度较高，那么可以转换一下求的数量，因为那是可以直接求到的，如枚举$k=2$时，就只需要求两个区间内的偶数数量，然后做组合数即可，两次除法一次乘法，从而从简单问题的角度解决了较难的问题（此处扩展来说就不一定是素数了，把1改成其他数即可）。唔 可能有人会问对应的$n$和$d$是什么，我也有这样的疑问，而我的想法是，$n$甚至可以是那段阶乘，所以实际计算过程需要遍历区间内每一个数。
那么回到笔试题目来，题目给出的是可能包含重复数的正整数数组，要求三元组，那么就使用同样的套路即可，尽管不是连续的整数，但是函数的表达还是一样的要求$gcd(a,b,c)==1$的数量，转换成求$1 | gcd(a,b,c)$的数量，然后套上莫比乌斯反演公式即可。而因为此处不是连续的数字，所以可能要花点功夫，因为数的范围还是1e5，因此可以将数都放到桶里面方便取，然后间隔着去找$gcd(a,b,c)=k % 1 == 0$的数量，如要$k$的，那就从$k$开始，取$k$, $2k$, $3k$的数即可，这里要注意一点就是，我们求的是$cd(a,b,c)=k % 1 == 0$的数量，因此尽管$buckets[k]$可能为0，但是那一系列数还是能取到满足要求的，那么是否会重复计数呢？公式里面其实就已经考虑了这个问题，所以不用担心（逃）。
代码如下，添加了一个暴力的用于检验答案对错。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstring>
#include <cstdlib>
using namespace std;
int (int x, int y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}
int baoli(const vector<int> &arr)
{
int ans = 0;
for (int i = 0; i < arr.size(); ++i)
{
for (int j = i + 1; j < arr.size(); ++j)
{
for (int k = j + 1; k < arr.size(); ++k)
{
if (gcd(gcd(arr[i], arr[j]), arr[k]) == 1)
{
ans++;
}
}
}
}
return ans;
}
const int maxn = 100000 + 10;
int buckets[maxn];
int mu[maxn], vis[maxn], primes[maxn];
int cnt;
void getmu()
{
memset(vis, 0, sizeof(vis));
memset(mu, 0, sizeof(mu));
cnt = 0;
mu[1] = 1;
for (int i = 2; i <= maxn; ++i)
{
if (!vis[i])
{
primes[cnt++] = i;
mu[i] = -1;
}
for (int j = 0; j < cnt && primes[j] * i <= maxn; ++j)
{
vis[primes[j] * i] = 1;
if (i % primes[j] == 0)
break;
mu[i * primes[j]] = -mu[i];
}
}
}
int maxi = 0, n = 0;
long long solve()
{
long long f = 0;
for (int i = 1; i <= maxi; ++i)
{
long long p = 0;
for (int j = i; j <= maxi; j += i)
{
p += buckets[j];
}
f += mu[i] * p * (p - 1) * (p - 2) / 6;
}
return f;
}
int main()
{
getmu();
cin >> n;
vector<int> arr(n);
memset(buckets, 0, sizeof(buckets));
srand(0);
for (int i = 0; i < n; ++i)
{
arr[i] = rand() % 100000 + 1;
buckets[arr[i]] += 1;
maxi = max(maxi, arr[i]);
}
cout << endl;
cout << solve() << endl;
return 0;
}
|
当然了，莫比乌斯反演其实也是对容斥问题的求解思路，因此，这道题也可以按照这个思路有容斥问题的解法，具体应该是选出3元组的方式的数量减去gcd不为1的数量，而遇到2，3得6这种情形，就要把6的那部分加回来（很像$mu$函数了…）。
还有一个算法复杂度的问题，就是solve那两重循环的复杂度应该是多少，实际上可以发现第二重循环时$ln(n)$的泰勒展开，所以整个复杂度时$O(nlog(n))$的，而莫比乌斯反演需要用到的$mu$的计算方法时$O(n)$的，所以整个算法复杂度是$O(nlog(n))$。
近期评论