CF585E Present for Vitalik the Philatelist 题解

CF585E Present for Vitalik the Philatelist

题意

• 有一个包含 $n$ 个 $\in [2, 10^7]$ 的整数的可重集合。
• 要求满足条件的一个元素 $x$ 和一个集合 $S$ 的方案数。
• 条件：$x \notin S$，$\gcd\\{S\\} > 1$，$\gcd(x, \gcd\\{S\\}) = 1$。
• $n \le 5 \times 10^5$，答案对 $10^9+7$ 取模。

题解

枚举 $d = gcd\\{S\\}$，设 $c$ 为 $d$ 的倍数的个数，则 $d$ 对应的方案数为 $(n-c) \times (2^c - 1)$。

显然有算重的，容斥一下即可，容斥系数恰好为莫比乌斯函数的相反数。

时间复杂度 $\mathcal O(w \log w)$。

代码

const int N = 5e5 + 7, M = 1e7 + 7;
int n, m, x, c[M], p[M], cnt, v[M];
modint num[N], miu[M], ans;

int main() {
	rd(n), num[0] = 1;
	for (int i = 1; i <= n; i++) rd(x), m = max(m, x), c[x]++, num[i] = num[i-1] * 2;
	miu[1] = 1;
	for (int i = 2; i <= m; i++) {
		if (!v[i]) v[i] = p[++cnt] = i, miu[i] -= 1;
		for (int j = 1; j <= cnt && i * p[j] <= m && p[j] <= v[i]; j++)
			v[i*p[j]] = p[j], miu[i*p[j]] = p[j] == v[i] ? 0 : -miu[i];
	}
	for (int i = 1; i <= m; i++) {
		cnt = 0;
		for (int j = i; j <= m; j += i) cnt += c[j];
		ans += (-miu[i]) * (n - cnt) * (num[cnt] - 1);
	}
	print(ans);
	return 0;
}