CF1780 F.Three Chairs - 题解

标签：pr CF1780 limits Chairs 题解 sum mu ++ int

给定数列 \(\{ a_n \}\)，求无序三元组 \((i, j, k)\) 的数量，满足 \(\gcd(\min(a_i, a_j, a_k), \max(a_i, a_j, a_k)) = 1\)，\(n \leq 3 \cdot 10^5, a_i \leq 3 \cdot 10 ^ 5\) 且 \(a_i\) 互不相同。

---

记 \([~]\) 为艾佛森括号，\(V = \max(a_i), e_i = [i \in \{a_n\}],s_i = \sum \limits_{j = 1} ^ i e_j\)。

考虑枚举 \((a_i, a_j, a_k)\) 中的最小值与最大值，记最大值为 \(i\)，最小值为 \(j\)，则第三个数值有 \(\sum \limits_{x = j + 1} ^ {i - 1} e_x = s_{i - 1} - s_j\) 种方案。容易得到如下结果。

\[Ans = \sum \limits_{i = 2} ^ {V} [e_i = 1]\sum \limits_{j = 1} ^ {i - 1} [e_j = 1][\gcd(i, j) = 1](s_{i - 1} - s_j) \]

对 \([\gcd(i, j) = 1]\) 作莫比乌斯反演，得

\[\begin{aligned} Ans &= \sum \limits_{i = 2} ^ {V} [e_i = 1]\sum \limits_{j = 1} ^ {i - 1} [e_j = 1](s_{i - 1} - s_j) \sum \limits_{d | i, d | j} \mu(d) \\ &= \sum \limits_{d = 1} ^ V \mu(d) \sum \limits_{i = 1} ^ {\lfloor \frac{V}{d} \rfloor} [e_{di} = 1]\sum \limits_{j = 1} ^ {i - 1} [e_{dj} = 1](s_{di - 1} - s_{dj})\\ &= \sum \limits_{d = 1} ^ V \mu(d) \sum \limits_{i = 1} ^ {\lfloor \frac{V}{d} \rfloor} ([e_{di} = 1] s_{di - 1} (i - 1) - \sum \limits_{j = 1} ^ {i - 1} [e_{dj} = 1] s_{dj}) \end{aligned} \]

括号内部的 \(\sum \limits_{j = 1} ^ {i - 1} [e_{dj} = 1] s_{dj}\) 可以随 \(i\) 的枚举递推，故由调和级数知计算该式的时间复杂度为 \(\mathcal{O}(n \log n)\)，可以通过本题。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int V = 3e5 + 10;
vector<int> pr, mu(V), vis(V);
void sieve(){
	mu[1] = 1;
	for(int i = 2; i < V; i++){
		if(!vis[i]) mu[i] = -1, pr.push_back(i);
		for(int j = 0; j < pr.size() && pr[j] * i < V; j++){
			vis[pr[j] * i] = 1;
			if(i % pr[j] == 0) break;
			mu[pr[j] * i] = -mu[i];
		}
	}
}
// 线性筛计算 mu 函数
void solve(){
	int n; cin >> n;
	vector<int> a(n), s(V, 0), exist(V, 0);
	for(int i = 0; i < n; i++)
		cin >> a[i], s[a[i]]++, exist[a[i]] = 1;
	for(int i = 1; i < V; i++) s[i] += s[i - 1];
	
	i64 ans = 0;
	for(int d = 1; d < V; d++){
		i64 r = 0, A = 0, e = 0;
		for(int i = 1; i * d < V; i++){
			if(!exist[i * d]) continue;
			r += 1LL * s[i * d - 1] * e - A;
			A += s[i * d];
			e++;
		}
		ans += mu[d] * r;
	}
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	sieve();
	solve();	
}

笔者为数不多的场切 \(2F\) 题，以此纪念

标签：pr,CF1780,limits,Chairs,题解,sum,mu,++,int
From： https://www.cnblogs.com/chroneZ/p/17067685.html