莫比乌斯反演

公式

形式1：
\(\;F(n) = \sum\limits_{d|n}f(d)\)
\(\;f(n) = \sum\limits_{d|n}\mu(d)F(\frac{n}{d})\)
\(\;\)证明：\(f(d) = \sum\limits_{d|n}\mu(d)F(\frac{n}{d}) = \sum\limits_{d|n}\mu(d)\sum\limits_{k|\frac{n}{d}}f(k) = \sum\limits_{k|n}f(k)\sum\limits_{d|\frac{n}{k}}\mu(d) = \sum\limits_{k|n}f(k)\)
\(\;\)这里用到了\(\sum\limits_{d|n}\mu(d) = [n=1]\)

形式1：
\(\;F(n) = \sum\limits_{n|d}f(d)\)
\(\;f(n) = \sum\limits_{n|d}\mu(\frac{n}{d})F(d)\)
\(\;\)证明同理
\(\;\)这是较常用的公式

莫比乌斯反演

原文：https://www.cnblogs.com/2016gdgzoi509/p/11186350.html