CF585E Present for Vitalik the Philatelist 题解
Visits: 738
题意
- 有一个包含 $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;
}
hankeke
2019年12月17日 下午2:44
我感觉您这个算法应该是 $O(w\log w)$ 的吧。您的 $i$ 从 $1$ 枚举到 $m$ 又枚举了 $i$ 的倍数,这是标准的调和级数吧。
xht37
2019年12月17日 下午4:30
fixed & thanks