RainAir
My OI Blog
RainAir
「CF803F」Coprime Subsequences

题目大意

给长度为 $n$ 的序列,询问有多少个子序列满足它们的 gcd 为 $1$。

题解

其实这篇博客是用来 的 (强行刷文章量)
我们设 $f(x)$ 表示 $gcd = x$ 的子序列的数量,那么可以立马启发我们设 $F(x)$ 表示 gcd 是 $x$ 的倍数的子序列数量,如果我们统计出 $cnt_i$ 表示 $i$ 和 $i$ 的倍数的数量,那么 $F(x) = 2^{cnt_x} – 1$。
又可以发现 $f(x)$ 和 $F(x)$ 满足关系 $F(x) = \sum_{d|x} f(d)$,也就有 $f(x) = \sum_{x|d} F(d)\mu(d)$,直接暴力算就可以了。。。(甚至不需要任何数论分块技巧,是一道小学组数论题)

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/804
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF803F」Coprime Subsequences
题目大意 给长度为 $n$ 的序列,询问有多少个子序列满足它们的 gcd 为 $1$。 题解 其实这篇博客是用来 水 的 (强行刷文章量) 我们设 $f(x)$ 表示 $gcd = x$ 的子序列的数量,那么可…
扫描二维码继续阅读
2019-08-27
标签
近期评论