莫比乌斯反演

还能不能愉快地学习信息了。。

天天学的都是数学。。

1.莫比乌斯函数

莫比乌斯函数的定义很简单

$$\mu(n)=\begin{cases}
1&n=1\\
(-1)^k&n为k个不同质数之积\\
0&其他情况\\
\end{cases}$$

它有一些神奇的性质:对于任意正整数n,

$$\sum_{d|n}\mu(d)=\begin{cases}
1&n=1\\
0&n\ne 1\\
\end{cases}$$

$$\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}$$

以及接下来的莫比乌斯反演

2.莫比乌斯反演

若对于两个数论函数\(f(n)\)和\(g(n)\)而言,有\(f(n)=\sum_{d|n}g(d)\)

那么同时有\(g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\)

也有另一种形式:若\(f(n)=\sum_{n|d}g(d)\)那么\(g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)\)

证明略去

3.应用

对于很多有关于\(gcd\)的题目莫比乌斯函数很好用然而不会用

数学很成问题啊。。

【BZOJ2005】【NOI2010】能量采集

【叉姐NOIP模拟赛】Lcmsum

说点什么

  Subscribe  
提醒