莫比乌斯反演小结

这里是简介

注意!!!!

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

狄利克雷卷积(符号:$\ast$)

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

则:

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

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

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

积性函数

如果$\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}$,即唯一分解定理)

$\sigma_0(n)=\prod_{i=1}^t(k_i+1)$,$\varphi(n)=\prod_{i=1}^tp_i^{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)$

好难啊

其他:整除分块

如果要你求一个东西:

你可能会说,这当然是$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);
}