CF585E Present for Vitalik the Philatelist 题解

作者: xht37 分类: 题解 发布时间: 2019-11-23 14:42

Visits: 738

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;
}
2条评论
  • hankeke

    2019年12月17日 下午2:44

    我感觉您这个算法应该是 $O(w\log w)$ 的吧。您的 $i$ 从 $1$ 枚举到 $m$ 又枚举了 $i$ 的倍数,这是标准的调和级数吧。

    1. xht37

      2019年12月17日 下午4:30

      fixed & thanks

发表评论

电子邮件地址不会被公开。 必填项已用*标注