莫比乌斯函数
定义
\[\mu(n)= \begin{cases} 1 &n=1 \\ 0 &n含有平方因子 \\ (-1)^k &k为本质不同的质因子个数 \end{cases} \]性质
莫比乌斯函数是积性函数，且有
\[\sum\limits_{d|n}\mu(d) \begin{cases} 1 &n=1\\ 0 &n\neq 1\\ \end{cases} \]即\(\sum\limits_{d|n}\mu(d)=\varepsilon(n)\)，卷积形式为\(\mu*1=\varepsilon\)
证明
设\(n=\prod\limits_{i=1}^{k}p_i^{c_i}，n'=\prod\limits_{i=1}^{k}p_i\)，有莫比乌斯函数的定义可知\(\sum\limits_{d|n}\mu(d)=\sum\limits_{d|n'}\mu(d)=\sum\limits_{i=0}^{k}C_k^i(-1)^i\)，（把枚举因数换了一种形式），根据二项式定理，\(\sum\limits_{i=0}^{k}C_k^i(-1)^i1^{k-i}=(1-1)^k\)，所以当\(k=0(n=1)\)时为1，其余为0。得证。
莫比乌斯变换
公式
1.若\(f(n)=\sum\limits_{d|n}g(d)\)，则\(g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})\)
2.若\(f(n)=\sum\limits_{n|d}g(d)\)，则\(g(n)=\sum\limits_{n|d}\mu(d)f(\frac{d}{n})\)
证明
1.\(\sum\limits_{d|n}\mu(d)f(\frac{n}{d})=\sum\limits_{d|n}\mu(d)\sum\limits_{k|\frac{n}{d}}g(k)=\sum\limits_{k|n}g(k)\sum\limits_{d|\frac{n}{k}}\mu(d)=\sum\limits_{k|n}g(k)\varepsilon(\frac{n}{k})=g(n)\)
2.\(\sum\limits_{n|d}\mu(d)f(\frac{d}{n})=\sum\limits_{k=1}^{+\infty}\mu(kn)f(k)=\sum\limits_{k=1}^{+\infty}\mu(kn)\sum\limits_{k|d}g(d)=\sum\limits_{n|d}g(d)\sum\limits_{kn|d}\mu(kn)=\sum\limits_{n|d}g(d)\sum\limits_{k|\frac{d}{n}}\mu(k)=\sum\limits_{n|d}g(d)\varepsilon(\frac{d}{n})=g(n)\)
常用套路
\([gcd(i, j) == 1]=\sum\limits_{d|gcd(i, j)}\mu(d)\)
例题待更……
标签：frac,limits,乌斯,sum,mu,莫比 From： https://www.cnblogs.com/sandom/p/16777187.html