莫比乌斯反演小结

这里是简介

注意！！！！

这里不是学习笔记，只是一些有关知识的总结！！

狄利克雷卷积（符号：$\ast$）

如果$\mathbf t=\mathbf f \ast \mathbf g$

则：

$$\mathbf t(n)=\sum_{d|n}\mathbf f(d)g(\frac{n}{d})$$

狄利克雷卷积还有以下性质：

交换律，结合律，分配率，等等….

一个函数（$\mathbf f$）的逆（$\mathbf g$）：即$\mathbf f \ast \mathbf g= \epsilon$ 单位元$\epsilon(n)=[n==1]$

$$\mathbf g(n)=\frac{1}{\mathbf f(1)}([n==1]-\sum_{d|n,d\neq1}\mathbf f(d)g(\frac{n}{d}))$$

积性函数

如果$\mathbf f(nm)=\mathbf f(n)\times \mathbf f(m) $ 则函数$\mathbf f$为完全积性函数。

如果再加上约束条件$n\perp m$，则函数为积性函数。一个完全积性函数一定是积性函数

积性函数的特殊性质：

1. 两个积性函数的狄利克雷卷积一定是积性函数
2. 任意一个积性函数$\mathbf f(1)=1$恒成立
3. 积性函数的逆一定是积性函数（可以在第二条性质的基础上证明）

一些常见的积性函数有（定义$n=\prod_{i=1}^tp_i^{k_i}$，即唯一分解定理）

$\sigma0(n)=\prod{i=1}^t(ki+1)$，$\varphi(n)=\prod{i=1}^tpi^{k_i-1}(p_i-1)=n\prod{i=1}^t(1-\frac{1}{p_i})$

莫比乌斯反演（摘自xgzc的博客）

定义一个函数$\mu$使得$\mu∗1=ϵ$，即$\mu$为$\mathbf 1(n)=\mathbf i\mathbf d^0(n)=1$的逆

这样的话，如果$\mathbf g∗\mathbf 1=\mathbf f$，则$\mathbf f∗\mu =\mathbf g$

即：如果$\mathbf f(n)=∑{d|n}\mathbf g(d)$，则$\mathbf g(n)=∑{d|n}\mu(d)\mathbf f(\frac nd)$

好难啊

其他：整除分块

如果要你求一个东西：

$$\sum_{i=1}^n \lfloor\frac ni \rfloor$$

你可能会说，这当然是$O(n)$求啊！！！

那么$n\leq 10^{14}$呢？？

你可能会说，我打了个表，发现在一段连续的区间内，函数值相同。但好像没有什么关系？？

不，根据前人的经验，每一个连续的区间，它的右界在$n/(n/i)$，所以，我们就可以在$O(\sqrt n)$算了。

比如说：

for(int l = 1; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}