莫比乌斯反演整理

UPD:我就是个菜鸡QAQ写的这些东西哎……太弱的时候什么都敢乱写……神犇看到就当开笑话嘛QAQ……求不喷

莫比乌斯反演通常是利用莫比乌斯函数来简化一类逆向求函数的问题。
设\(F(n)\)与\(f(n)\)是定义在自然数集合上的两个数论函数,并且满足条件$$
F(n) = \sum_{d|n}f(d)
$$或者$$
F(n) = \sum_{n|d}f(d)
$$已知的\(F(n)\),求\(f(n)\)的表达式。

观察\(F(n)\)式:\(F(n)\)被\(F(xn)(x > 1)\)所包含。所以,只需类似解多元一次方程一样,通过抵消系数的方法(容斥)就可以逐个求出\(f(n)\)。
但是这样太慢了!于是我们想加速这个过程。
我们希望,存在一个函数,使得\(F(n)\)可以直接被表示出来。 (更多…)



ˆ Back To Top