mobius反演小结

最近遇到了好多用到mobius反演的题目，在这里总结一下。

mobius反演的精髓就在于根据题意构造两个函数f(n)和F(n),其中F(n)有显表达式,并且有

$$F(n) = \sum\limits_{d \mid n} f(d)$$

这样，我们就可以通过反演得出

$$f(n) = \sum\limits_{d | n} \mu(d) F(\frac{n}{d})$$

有时，mobius反演还有另外一种写法：

$$F(n) = \sum\limits_{n | d} f(d) \Rightarrow$$

$$f(n) = \sum\limits_{n | d} \mu(\frac{d}{n})F(d)$$

上述公式中的$\mu(d)$称为$mobius$函数。它的定义为

若$d = 1$，则$\mu(d) = 1$
若$d = p_1 × p_2 × p_3 × \dots × p_k$， $p_i$均为互异质数，则$\mu(d) = (-1)^k$
否则，$\mu(d) = 0$

根据这个定义我们可以通过$Euler$筛法以$O(n)$的时间复杂度求出$\mu$函数。

int p[M], miu[N], tot;
bool flag[N];
void mobius() {
	memset(flag, 0, sizeof(flag));
	tot = 0;
	miu[1] = 1;
	for (int i = 2; i < N; ++i) {
		if (!flag[i]) {
			p[tot++] = i;
			miu[i] = -1;
		}
		for (int j = 0; j < tot && i * p[j] < N; ++j) {
			flag[i * p[j]] = true;
			if (i % p[j]) {
				miu[i * p[j]] = -miu[i];
			}
			else {
				miu[i * p[j]] = 0;
				break;
			}
		}
	}
}

不过仅仅求出$\mu$函数并不能解决我们的问题。考察$mobius$反演的题目往往是要根据给出的情境，构造出两个满足要求的函数，之后可能还需要针对反演后的式子做进一步的化简。

下面通过几个例题来学习一些$mobius$反演中构造$F(n)$、$f(n)$的技巧。