本文共 1819 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要计算给定数组中互素数对的数量。互素数对指的是两个数的最大公约数为1的对。我们可以利用莫比乌斯函数和容斥原理来高效地解决这个问题。
莫比乌斯函数：这个函数用于帮助我们通过容斥原理来计算互素数对的数量。莫比乌斯函数 mu(d) 的值取决于 d 的质因数分解情况：
d 有平方因子，mu(d) = 0。mu(d) 为 (-1)^k，其中 k 是 d 的不同质因数的个数。容斥原理：我们可以利用莫比乌斯函数来计算互素数对的数量。具体来说，互素数对的数量可以表示为：[\text{总对数} = \sum_{d=1}^{max_a} \mu(d) \times C(\text{cnt}[d], 2)]其中，cnt[d] 表示数组中被 d 整除的数的个数，C(cnt[d], 2) 是从 cnt[d] 个数中选出两个的组合数。
步骤：
d 的 cnt[d]，即数组中被 d 整除的数的个数。#include#include #include #include using namespace std;const int MAXN = 100010;int mu[MAXN];void compute_mobius(int n) { mu[1] = 1; vector is_prime(n + 1, true); is_prime[1] = false; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { for (int j = i; j <= n; j += i) { is_prime[j] = false; mu[j] = -mu[j / i]; if (j % i == 0) { mu[j] = 0; } } } }}int main() { compute_mobius(MAXN); while (~scanf("%d", &n)) { vector a(n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } int max_a = *max_element(a.begin(), a.end()); vector freq(max_a + 1, 0); for (int num : a) { freq[num]++; } vector cnt(max_a + 1, 0); for (int d = 1; d <= max_a; ++d) { for (int j = d; j <= max_a; j += d) { cnt[d] += freq[j]; } } long long ans = 0; for (int d = 1; d <= max_a; ++d) { if (cnt[d] >= 2) { ans += (cnt[d] * (cnt[d] - 1) / 2) * mu[d]; } } cout << ans << endl; } return 0;}
mu 数组，标记每个数的质因数情况。a。cnt 数组：统计每个 d 的倍数出现次数。这种方法高效地解决了问题，能够在合理的时间和空间复杂度内处理大规模输入。
转载地址：http://eznfk.baihongyu.com/