莫比乌斯反演学习笔记

tony102

2020 年 11 月 14 日

1922 次浏览

暂无评论

716字数

总结

## 莫比乌斯函数

### 定义

定义函数 $\mu (d)$

$$
\begin{equation}
\mu(d)=
\left\{
             \begin{array}{lr}
             1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d=1\\
             (-1)^k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d= \prod_{i=1}^{k} p_i \ \& \ \forall i,j \in [1,k], p_i \not= p_j \\
             0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall c_i \geq 2
             \end{array}
\right.
\end{equation}
$$

还有一些常用的性质

1. 最常用的: $\forall n \in N, \sum_{d|n} = [n=1]$
2. $\forall n \in N, \sum_{d|n} \frac{\mu (d)}{d} = \frac{\varphi(n)}{d}$

~~均不会证~~

#### Code

```cpp
inline void getMu()
{
	int siz = 10000000;
	isPrime[1] = mu[1] = 1;
	for (register int i = 2; i <= siz; ++ i) {
		if (!isPrime[i]) {
			prime[++ tot] = i, mu[i] = -1;
		}
		for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) {
			isPrime[i * prime[j]] = 1;
			if (i % prime[j]) mu[i * prime[j]] = -mu[i];
			else {
				mu[i * prime[j]] = 0;
				break;
			}
		}
	}
}
```

## 莫比乌斯反演

### 定理

设两个单元函数 $F(x)$ , $f(x)$ 分别为

$$
F(x) = \sum_{d\mid n} f(d)
$$

那么

$$
f(x) = \sum_{d|n} \mu(d) F(\lfloor \frac{n}{d} \rfloor)
$$

## Summary

其实你根本不需要会这个反演,只需要知道上面那个最常用的性质就可以了

基本的东西做几个题就会了

最后修改：2021 年 09 月 04 日