莫比乌斯反演学习笔记

引子

很久以前就听说过了莫比乌斯反演这个名词，每次都看的稀里糊涂，但一直没能学下去。也碰到不少莫比乌斯反演的题目，无奈只能跳过。最近各种爆炸，心态极端不好，几度想放弃，想来想去还是应该坚持下去，学点新东西。于是再次百度一些以前遗留下来没学完的知识点。
主要学习了
@litble 初涉莫比乌斯反演（附带例题）
@outer_form 莫比乌斯反演定理证明（两种形式）

基本知识

莫比乌斯反演初始是两个相互关联的函数 F(x) $F\left(x\right)$和 f(x) $f\left(x\right)$，

形式1

一种形式是已知

形式2

另一种形式是已知

莫比乌斯函数 μ(x) $\mu \left(x\right)$性质

1.

2.

开始反演

形式1

形式2

关于③到④的自我理解和解释
对于③，当且仅当 kn|d′ $kn|d^{\prime }$时对答案有 μ(k)∗f(d′) $\mu \left(k\right)\ast f\left(d^{\prime }\right)$的贡献。
且 n $n$对于要证明的式子为常数， k取遍[1,+∞)的每一个整数,d′取遍(kn)的所有倍数 $k取遍[1,+\infty )的每一个整数,d^{\prime }取遍\left(kn\right)的所有倍数$ flag A
对与④，
k|d′n⟺kn|d′ $k|\frac{d^{\prime }}{n}⟺kn|d^{\prime }$
kn|d′⟹n|d′ $kn|d^{\prime }⟹n|d^{\prime }$
所以当且仅当 kn|d′ $kn|d^{\prime }$成立时才会对答案有 f(d′)×μ(k) $f\left(d^{\prime }\right)\times \mu \left(k\right)$的贡献。
d′取遍n的所有倍数,k取遍d′n的所有因数 $d^{\prime }取遍n的所有倍数,k取遍\frac{d^{\prime }}{n}的所有因数$ flag B
现在只需要证明
满足 flag A 的所有序偶(数对) <k,d′> $<k,d^{\prime }>$构成的集合A
和
满足flag B的所有序偶(数对) <k,d′> $<k,d^{\prime }>$构成的集合B
是相等的即可。
以下字母若无特殊说明，取值范围皆是正整数
A={<k,d′>|kn|d′} $A=\{<k,d^{\prime }>|kn|d^{\prime }\}$
B={<k,d′>|n|d′且k|d′n} $B=\{<k,d^{\prime }>|n|d^{\prime }且k|\frac{d^{\prime }}{n}\}$
又 k|d′n⟺kn|d′⟹n|d′ $k|\frac{d^{\prime }}{n}⟺kn|d^{\prime }⟹n|d^{\prime }$
所以 B={<k,d′>|kn|d′} $B=\{<k,d^{\prime }>|kn|d^{\prime }\}$
显然 A=B $A=B$
因此③可以到④

④到⑤和前面的类似，当且仅当 d′n=1 $\frac{d^{\prime }}{n}=1$, ∑k|d′nμ(k)≠0 $\sum _{k|\frac{d^{\prime }}{n}}\mu \left(k\right)\ne 0$
因此 d′=n $d^{\prime }=n$才有意义，代入很快化为 f(n) $f\left(n\right)$

莫比乌斯函数的求法

注意到莫比乌斯函数的条件积性，对欧拉筛熟悉的不难时空复杂度皆为 O(n) $O\left(n\right)$预求出 μ(1) $\mu \left(1\right)$~ μ(n) $\mu \left(n\right)$

先提交以下，后面再补代码和题目
逃
2018-09-13 11:44:55