作为试验一份

本文主要是介绍作为试验一份，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

随便贴一下而已

莫比乌斯函数

不知道是不是受那个带子的影响，莫比乌斯这个名字有种扭曲的美感，莫比乌斯函数也是这样。莫比乌斯函数 μ ( d ) \mu(d) μ(d) 是这样定义的：

∑ d ∣ m μ ( d ) = [ m = 1 ] \sum_{d| m}\mu(d)=[m=1] d∣m∑​μ(d)=[m=1]

其中方括号是《具体数学》中使用的艾弗森约定（我不知道这种形式是不是惯例），如果其中的命题为真的话这个函数为1，否则为0。换句话说也就是只有当 m=1 的时候为 1，其余都是 0。这种递归式并不是很好求值，尤其是累加记号中涉及到整除操作时。我们可以写出前几项看看：

这东西看上去很随机还没啥用… 不过很快我们就会看到它存在的意义，而且这个东西还有一个很厉害的名字：

莫比乌斯反演

这种说法听起来就像某种奇幻背景的故事中的设定，以至于和这种名字放在一起没有什么违和感：

「神的不在场证明」！

「九天雷霆双脚蹬」！

「莫比乌斯反演」！

（好像也没有那么中二？）总之莫比乌斯函数遵循着如下的反演原理：

g ( m ) = ∑ d ∣ m f ( d ) ⇔ f ( m ) = ∑ d ∣ m μ ( d ) g ( m d ) g(m)=\sum_{d|m}f(d)\Leftrightarrow f(m)=\sum_{d|m}\mu(d)g\left(\frac md\right) g(m)=d∣m∑​f(d)⇔f(m)=d∣m∑​μ(d)g(dm​)

这看起来还是很有用的（虽然除了欧拉函数我也没见过多少这种形式的函数）要证明这个式子我们还是要花点技巧的：

∑ d ∣ m μ ( d ) g ( m d ) = ∑ d ∣ m μ ( m d ) g ( d ) ( ∑ d ∣ m f ( d ) = ∑ d ∣ m f ( m / d ) ) = ∑ d ∣ m μ ( m d ) ∑ k ∣ d f ( k ) = ∑ k ∣ m ∑ l ∣ ( m / k ) μ ( m k l ) f ( k ) ( ∑ d ∣ m ∑ k ∣ d a d , k = ∑ k ∣ m ∑ l ∣ ( m / k ) a k l , k ) = ∑ k ∣ m ∑ l ∣ ( m / k ) μ ( l ) f ( k ) = ∑ k ∣ m [ m / k = 1 ] f ( k ) = f ( m ) \begin{aligned} \sum_{d|m}\mu(d)g\left(\frac md\right)=&\sum_{d|m}\mu\left(\frac md\right)g(d)\qquad\qquad\left(\sum_{d|m}f(d)=\sum_{d|m}f(m/d)\right)\\ =&\sum_{d|m}\mu\left(\frac md\right)\sum_{k|d}f(k)\\ =&\sum_{k|m}\sum_{l|(m/k)}\mu\left(\frac m {kl}\right)f(k)\quad\left(\sum_{d|m}\sum_{k|d}a_{d,k}=\sum_{k|m}\sum_{l|(m/k)}a_{kl,k} \right)\\ =&\sum_{k|m}\sum_{l|(m/k)}\mu(l)f(k)\\ =&\sum_{k|m}[m/k=1]f(k)=f(m) \end{aligned} d∣m∑​μ(d)g(dm​)=====​d∣m∑​μ(dm​)g(d)⎝⎛​d∣m∑​f(d)=d∣m∑​f(m/d)⎠⎞​d∣m∑​μ(dm​)k∣d∑​f(k)k∣m∑​l∣(m/k)∑​μ(klm​)f(k)⎝⎛​d∣m∑​k∣d∑​ad,k​=k∣m∑​l∣(m/k)∑​akl,k​⎠⎞​k∣m∑​l∣(m/k)∑​μ(l)f(k)k∣m∑​[m/k=1]f(k)=f(m)​

可能需要补充的一点：右侧第二个式子的本质就是改名与整除的传递性。不过事实上吸引莫比乌斯发现（发明？用词取决于读者的数学观）这个函数的是另一个反演性质：

g ( x ) = ∑ d ⩾ 1 f ( x / d ) ⇔ f ( x ) = ∑ d ⩾ 1 μ ( d ) g ( x / d ) g(x)=\sum_{d\geqslant 1}f(x/d)\Leftrightarrow f(x)=\sum_{d\geqslant 1}\mu(d)g(x/d) g(x)=d⩾1∑​f(x/d)⇔f(x)=d⩾1∑​μ(d)g(x/d)

这个性质的证明也很简短：

∑ d ⩾ 1 μ ( d ) g ( x / d ) = ∑ d ⩾ 1 μ ( d ) ∑ k ⩾ 1 f ( x / d k ) = ∑ l ⩾ 1 ( x / l ) ∑ d , k ⩾ 1 μ ( d ) [ l = d k ] ( 这 种 换 元 . . . ) = ∑ m ⩾ 1 f ( x / m ) ∑ d ∣ m μ ( d ) = f ( x ) \begin{aligned} \sum_{d\geqslant1}\mu(d)g(x/d)=&\sum_{d\geqslant1}\mu(d)\sum_{k\geqslant1}f(x/dk)\\ =&\sum_{l\geqslant1}(x/l)\sum_{d,k\geqslant1}\mu(d)[l=dk]\quad(这种换元...)\\ =&\sum_{m\geqslant1}f(x/m)\sum_{d|m}\mu(d)=f(x) \end{aligned} d⩾1∑​μ(d)g(x/d)===​d⩾1∑​μ(d)k⩾1∑​f(x/dk)l⩾1∑​(x/l)d,k⩾1∑​μ(d)[l=dk](这种换元...)m⩾1∑​f(x/m)d∣m∑​μ(d)=f(x)​

不过我没什么头绪… 或许是饿了，不过更有可能是太缺乏练习了。习题什么的下回再写，我们下次再见（笑）

2022-02-19

这篇关于作为试验一份的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！