RainAir
My OI Blog
RainAir

莫比乌斯反演
文章归档

「CF803F」Coprime Subsequences

题目大意 给长度为 $n$ 的序列,询问有多少个子序列满足它们的 gcd 为 $1$。 题解 其实这篇博客是用来 水 的 (强行刷文章量) 我们设 $f(x)$ 表示 $gcd = x$ 的子序列的数量,那么可以立马启发我们设 $F(x)$ 表示 gcd 是 $x$ 的倍数的子序列数量,如果我们统计出 $…

   164   2019-08-27   164 去吊打作者

「数学基础」莫比乌斯反演

UPD:狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。 积性函数 定义 对于一个函数 $f$,若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$,则我们称这样的函数为积性函数。 举例:$\phi(x),\mu(i),d_k(n)$($n$ 的所有正因子 $k$ 次幂和) 性质 若 $f(x)$ 为积…

   868   2019-01-14   868 去吊打作者
标签
近期评论