Mobius Inversion
2024-02-05 20:49:28
# Before-2024
Something useful
- 只有种取值
- 对于,是与被除并下取整取值相同的一段区间的右端点
Möbius function
用表示莫比乌斯函数。
一个有用的性质
证明:考虑相当于在的因子中选择若干个,然后把这些因子组成的数的加起来,如果有一个数的次数大于,对答案没有贡献,所以这个值只与选择的质因子的个数的奇偶性有关,也就是说只考虑每个质因子是否选择。
1 | IL void Sieve() { |
Dirichlet product
记为数论函数,定义
狄利克雷卷积满足交换律,结合律和分配率。
常见的积性函数:
- ,莫比乌斯函数。
- ,欧拉函数。
- ,约数个数。表示 的约数的个数。
- ,约数和函数。表示 的各个约数之和。
常见的完全积性函数:
常用的狄利克雷卷积:
Möbius inversion formula
对于数论函数
然后得到了
对于另一个式子
Tricks
设表示集合中的倍数的数的的个数,表示的数的个数(我们要求的答案是)。
小技巧:
记为的约数个数,因为
对于所有,预处理。
预处理可以枚举质数然后用调和级数,同时也可以在线筛的时候算。
考虑,加入会让,之前的变为,贡献为,
如果,加入让除了的所有因子上有一个,此时
同上,我们可以预处理
由于是积性函数,也是积性函数,所以是积性函数
对于,由于以上都是0,对答案无贡献。
一般地
Du’s Sieve
- 前缀和
考虑右边式子,由于是,所以只有种不同的取值,是一个前缀和的性质,于是可以递归求,求的过程中用hash表实现记忆化防止复杂度退化。
时间复杂度
注意到比较小的时候可以线性筛出来。
根据均值不等式当有最低复杂度
- 做法和复杂度同上。
1 | int sieveMu(int n) { |