目录
知识点：枚举，容斥。
原题面：https://codeforces.com/contest/1780/problem/F。
涉及 \(\gcd\) 的枚举的常见套路 + 似乎不太常见的容斥（？）
以及一种和题解原理相同但更好写的写法。
省流版：容斥的本质是把一个不重不漏的集合的并的贡献，转化成多个集合的交的贡献的和。
简述
给定一长度为 \(n\) 的数列 \(a\)，保证所有数两两不同。求满足：\(\gcd\left( \operatorname{min}(a_i, a_j, a_k), \max(a_i, a_j, a_k) \right) = 1\) 的三元组 \((i, j, k)\) 的数量。
\(3\le n\le 3\times 10^5\)，\(1\le a_i\le 3\times 10^5\)。
1S，256MB。
分析
先排序，以下钦定三元组 \((i,j,k)\) 中 \(i<j<k\)。然后考虑枚举三元组中的最大值 \(a_k\) 和最小值 \(a_i\)，如果 \(\gcd(a_i, a_k) = 1\)，那么它们对答案的贡献显然为可供选择的 \(a_j\) 的数量：\(k - i - 1\)，则仅需统计 \((a_i, a_k)\) 这种互质对的贡献。
考虑求得一个数组 \(f\)，\(f_k\) 代表以 \(a_k\) 为较大元素的满足条件的三元组的数量。以 \(a_k\) 为较大元素的数对总数为 \(\frac{(i-2)(i-1)}{2}\)，考虑问题的反面求非互质对的数量。套路地考虑枚举质因数 \(g\)，检查 \(a\) 中是否存在 \(g\) 的倍数，并令较大的倍数减去较小的倍数的贡献。具体地，对于小于 \(a_k\) 的 \(c\) 个与 \(a_k\) 不互质的 \(a_i\)，\(f_k\) 的贡献应减去 \(c\times (k - 1) - \sum i\)。
但在枚举质因数 \(g\) 的过程中，可能会出现 \(a_i\) 重复统计的情况。比如 \(g = 2\) 和 \(g = 3\) 均是 \(a_i = 6\) 的约数，使得 \(a_i=6\) 的贡献被 \(a_i\) 的倍数减去了两次。
考虑容斥。考虑扩大枚举 \(g\) 的范围，对于一对 \((a_i,a_k)\)，如果它们共同的质因数为 \((p_1, p_2,\dots, p_q)\)，那么减去枚举到它们时 \(a_i\) 对 \(f_k\) 的贡献后，应再加上枚举到 \(p_1\times p_2,p_1\times p_3,\cdots p_{q-1}\times p_q\) 的时 \(a_i\) 对 \(f_k\) 的贡献，再减去枚举到 \(p_1\times p_2\times p_3,p_1\times p_2\times p_4,\cdots p_{q-2}\times p_{q-1}\times p_q\) 的时 \(a_i\) 对 \(f_k\) 的贡献，……这样可以保证 \(a_i\) 的贡献最终只会被减去 1 次。总结一下，我们考虑枚举共同的质因数——如果 \(g\) 仅由 \(l\) 个质数的一次方构成，那么枚举到 \(g\) 时，\(a_i\) 对 \(f_k\) 贡献的符号应为 \((-1)^{l}\)，否则枚举到 \(g\) 时不统计贡献。
原理的话……学艺不精没法很好地解释。可以考虑质因数分解为 \((p_1, p_2, \dots, p_q)\) 中任意非空子集的数的集合 \(\{ a_i\}\)，满足：
\[A_l = \left\{ x \mid (p_i\mid x) \land (x \in a) \right\} \]\[\{ a_i\} = {\displaystyle \left|\bigcup _{l=1}^{q}A_l\right|=\sum _{l=1}^{n}(-1)^{l+1}\left(\sum _{1\leq u_{1}<\cdots <u_{l}\le q}\left|A_{u_{1}}\cap \cdots \cap A_{u_{l}}\right|\right)} \]上式中 \(\left|\bigcup _{l=1}^{q}A_l\right|\) 即 \(f_k\) 应当减去贡献的 \(a_i\) 的不重不漏的集合，我们的目标是把它们的贡献仅减去 1 次。考虑这个经典式子的意义，达成上述目的，等效于把所有集合 \(\left|A_{u_1}\cap \cdots \cap A_{u_l}\right|\) 的贡献减去 \((-1)^l\) 次。
\(\left|A_{u_1}\cap \cdots \cap A_{u_l}\right|\) 表示作为 \(p_{u_1}\times,\dots, p_{u_l}\) 的倍数的 \(a_i\) 的集合。而 \(p_{u_1}\times,\dots, p_{u_l}\) 共有 \(C_q^l\) 种。我们不妨把上面的式子写的更抽象一点：
\[-1 = -\sum_{l=1}^{q}(-1)^{l+1} C_{q}^l = \sum_{l=1}^{q}(-1)^{l} C_{q}^l \]\(C_q^l\) 即由 \(l\) 个质数的一次方构成的 \(g\) 的个数。由这个式子可知，令 \(f_k\) 减去所有 \(a_i\) 的贡献 1 次，等效于先枚举 \(g\)，并令 \(f_k\) 减去所有作为 \(g\) 的倍数的 \(a_i\) 的贡献 \((-1)^l\) 次。
实现时使用埃氏筛，处理出每个数的质因数同时标记不符合枚举条件的 \(g\)，再枚举合法的 \(g\) 的倍数更新即可。
总复杂度为 \(O(n\ln\ln n)\) 级别。
代码
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN], pos[kN];
LL ans, f[kN];
bool vis[kN], vis1[kN];
std::vector <int> p[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
if (i >= 3) f[i] = 1ll * (i - 2) * (i - 1) / 2ll;
}
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++ i) pos[a[i]] = i;
for (int i = 2; i <= a[n]; ++ i) {
if (vis1[i]) continue;
if (!vis[i]) p[i].push_back(i);
int sz = p[i].size();
LL cnt = (pos[i] > 0), sum = pos[i];
for (int j = 2; i * j <= a[n]; ++ j) {
vis[i * j] = 1;
if (!vis[i]) p[i * j].push_back(i);
if (j % i == 0) vis1[i * j] = 1;
if (pos[i * j]) {
f[pos[i * j]] += (sz % 2 ? -1 : 1) * (cnt * (pos[i * j] - 1ll) - sum);
++ cnt, sum += pos[i * j];
}
}
}
for (int i = 1; i <= n; ++ i) ans += f[i];
printf("%lld\n", ans);
return 0;
}