狄利克雷卷积和莫比乌斯反演

作者: dachengquan | 来源:发表于2020-08-04 20:28 被阅读0次

狄利克雷卷积和莫比乌斯反演
莫比乌斯变换-1-经典形式与狄利克雷卷积
莫比乌斯反演
莫比乌斯反演+模板
34-tidytext包学习：主题建模
「罗马人的故事11-13」：皇帝尤利安？他也配做皇帝吗？
莫比乌斯反演-从基础开始
POI 2007 ZAP - 莫比乌斯反演
狄利克雷卷积的运算律
莫比乌斯反演-2-拓展形式

积性函数

定义

一个数论函数f， $\forall (n,m)=1$ ，有 $f(nm)=f(n)×f(m)$ ，那么称f为积性函数。
一个数论函数f，对于 $\forall n,m$ ，有 $f(nm)=f(n)×f(m)$ ，那么称f为完全积性函数
其中数论函数的含义是

在数论上，算术函数（或称数论函数）指定义域为正整数、陪域为复数的函数，每个算术函数都可视为复数的序列。

主要概念就是定义域是正整数。

性质

性质：若f(x)，g(x)是积性函数那么下面的函数都是积性函数
$h(x) = f(x^p)$
$h(x) = f^p(x)$
$h(x) = f(x)g(x)$
$h(n) = \sum_{d\mid n}f(d)g(\frac n d)$
证明方法可以将x拆分为两个数a，b满足a*b=x,(a,b)=1。然后验证h(x) = h(a)*h(b)就可以了。最后一个同样可以拆分。
$h(ab) = \sum_{d\mid ab}f(d)g(\frac {ab} d)$
$h(b)*h(b) = (\sum_{d_1\mid b}f(d_1)g(\frac {b} {d_1}))*(\sum_{d_2\mid a}f(d_2)g(\frac {a} {d_2}))$
$h(b)*h(b) = \sum_{d\mid ab}f(d)g(\frac {ab} d)$
可以这样想d是a*b的正约数， $d_1$ 是a的正约数， $d_2$ 是b的正约数。(a,b)=1,所以 $d_1和d_2$ 不包含相同的质因数。a*b的正约数是 $d=d_1*d_2$

举例

常见的积性数论函数
单位函数 $\epsilon(n) = [n=1]$
常数函数 $1(n)=1$
恒等函数 $id(n) = n$
莫比乌斯函数 $\mu(n)= \begin{cases} 1 & n = 1\\ (-1)^k & n = p_1*p_2*...*p_k \forall p_i \neq p_j\\ 0 & others \end{cases}$
欧拉函数 $\varphi(n) = \sum_{i=1}^n [(i,n)=1]$
除数函数： $\sigma_{k}(n) = \sum _{d\mid n} d^k当k取0时，记作d(n)当k取1记作\sigma (n)$
其中莫比乌斯函数是当n=1时为1，对于任意一个质数p，如果 $p|n$ ,但是 $p^2\nmid n$ 也就是说对n进行质因数分解后，不含有相同的质因数的时候莫比乌斯函数为 $(-1)^k$ ,k是分解后质因数的个数，其他情况为0。除数函数k为0的时候求的是正约数的数量，k为1的时候求的是正约数的和。单位函数[n=1]的含义是n=1的时候为1，否则为0，就是布尔运算。欧拉函数的（i,n）=1是gcd(i,n)=1。

狄利克雷卷积

定义

两个数论函数f(x),g(x)的狄利克雷卷积是
$h(x) = (f*g)(x) = \sum _{d\mid n}f(d)*f(n/d) = \sum _{a*b=n}f(a)*g(b)$

性质

交换律： $f*g= g*f$
结合律： $(f*g)*h = g*(f*h)$
分配律： $f*(g+h) = f*g+f*h$
单位元： $f*\epsilon = f$
逆元：对于每个 $f(1)\neq1$ 的数论函数都有 $f*g=\epsilon$

交换律证明： $(f*g)(x) = \sum _{a*b=n}f(a)*g(b) = \sum _{a*b=n}g(a)*f(b)=(g*f)(x)$
结合律证明： $((f*g)*h)(n) = \sum _{d*c=n}(f*g)(d)*g(c) = \sum _{d*c=n}(\sum _{a*b=d} f(a)*g(b))*g(c)$
$= \sum_{a*b*c=n}f(a)*g(b)*h(c)$
剩下的写一下公式就可以推导出来。

卷积关系

$\epsilon = \mu*1$
$d=1*1$
$\sigma = id*1$
$\varphi = \mu * id$

$\epsilon = \mu*1$ 证明
$f = (\mu * 1) (n)=\sum_{d\mid n} \mu(d)$ ,根据积性函数的性质得到f也是积性函数，上面已经证明过了，在证明一次因为 $\forall (a,b)=1,a*b=n$ , $f(n) = \sum_{d\mid a*b} \mu(d) = ( \sum_{d\mid a} \mu(d))*( \sum_{d\mid b} \mu(d))=f(a)*f(b)$ 。那么对n进行质因数分解 $n=p_1^{c_1}*p_2^{c_2}*...*p_m^{c_m}$ , $f(n) = f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_m^{c_m})$ ,单独考虑每一个 $f(p^c) = \sum _{d|p^c}\mu (d) = \sum_{i=0}^c \mu(p^i)$
$\sum_{i=0}^c \mu(p^i)$ 单独来看这个公式， $\mu(1) = 1,\mu(p)=-1,\mu(p^2) = 0,....$ ，所以 $\sum_{i=0}^c \mu(p^i) = 0$ 带回 $f(n)$ 中得到f(n)=0，证明完毕。
得到 $\epsilon = \mu*1 = \sum_{d\mid n} \mu(d)$

$d=1*1$ 证明
$(1*1)(n) = \sum_{d\mid n}1(d)*1(n/d) = \sum_{d\mid n} 1 = d(n)$

$\sigma = id*1$ 证明
$(id*1)(n) = \sum_{d\mid n} id(d)*1(n/d) = \sum_{d\mid n}d = \sigma(n)$

$\varphi = \mu * id$
$1*\varphi =1*\mu * id = id$
只需要证明 $1*\varphi = id$ 即可。
我们知道 $f(n) = (1*\varphi)(n) = (\varphi * 1)(n) = \sum_{d\mid n}\varphi(d)$ 根据积性函数的性质可知， $\sum_{d\mid n}\varphi(d)$ 也是积性函数。那么对n进行质因数分解 $n=p_1^{c_1}*p_2^{c_2}*...*p_m^{c_m}$ , $f(n) = f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_m^{c_m})$ ,单独考虑每一个 $f(p^c) = \sum _{d|p^c}\varphi (d) = \sum_{i=0}^c \varphi(p^i) = \varphi(p^0)+\varphi(p^1)+...+\varphi(p^c)$ ,单独考虑 $\varphi(p^0)=1，\varphi(p^1)=p-1,\varphi(p^2) = p*(p-1),\varphi(p^c) = p^{c-1}*(p-1)$ 所以 $\sum_{i=0}^c \varphi(p^i)=p^c，f(p^c)=p^c带回f(n)中得到f(n)=n$ , $(1*\varphi)(n) = id(n)$ 证明完毕。

莫比乌斯反演

莫比乌斯函数
$\mu(n)= \begin{cases} 1 & n = 1\\ (-1)^k & n = p_1*p_2*...*p_k \forall p_i \neq p_j\\ 0 & others \end{cases}$
第二情况是n可以被分解为k个质数，并且这k个质数两两不同。
显然莫比乌斯函数满足 $p\nmid n,p\in prime$ 的时候 $\mu(n*p) = -\mu(n)$ 成立。
$p\mid n,p\in prime$ 的时候 $\mu(n*p) = 0$ 显然我们可以用线筛 $O(n)$ 的时机求1~n,
之间的莫比乌斯函数。绝大部分积性函数都可以O(n)的使用线筛时间内求出。
莫比乌斯推论，我们有 $\mu * 1 = \epsilon$
也就是 $(\mu * 1)(n) = \epsilon(n)$ 但是我们可以对他进行转换
$(\mu * 1)(gcd(a,b)) = \epsilon(gcd(a,b)) = [gcd(a,b) = 1] = \sum_{d\mid gcd(a,b) }\mu(d)$
对于某些a，b我们可以求出互质的个数。

莫比乌斯反演定理

假设有两个数论函数f，F满足
$F(n) = \sum_{d\mid n}f(d)$
那么有
$f(n) = \sum_{d\mid n}\mu(d)F(\frac n d)$

狄利克雷卷积证明：
$F = f*1$
$F *\mu= f*1*\mu$
$f = \mu * F$

其他证明方法：
$\sum_{d\mid n}\mu(d)F(\frac n d)=$
将 $F(n) = \sum_{d\mid n}f(d)$ 带入
$\sum_{d\mid n}\mu(d)(\sum_{p\mid \frac n d}f(p))=$
因为能对结果产生贡献必须满足（d*p）|n也就是 $\mu(d)*f(p)$ ，因此换一种形式也是正确的。
$\sum_{p\mid n}f(p)(\sum_{d\mid \frac n p}\mu(d))=$
根据上面验证的 $\sum_{d\mid n}\mu(d) = \epsilon(n)$ 可以得知，只有n=1的时候对最后的结果有贡献，也就是p=n
$f(n)$

莫比乌斯反演的另一种形式
$F(n)=\sum_{n|d}f(d)$
$f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$

狄利克雷卷积和莫比乌斯反演
积性函数定义一个数论函数f，，有，那么称f为积性函数。一个数论函数f，对于，有，那么称f为完全积性函数其中数...
莫比乌斯变换-1-经典形式与狄利克雷卷积
经典形式设定义在正整数集合上，如果：称作是的和函数[1]。此时，无论是什么，都有如下公式成立： ...
莫比乌斯反演
适用题目特征常见和式常见和式常见和式常见和式其中表示的约数个数。常见和式原理例题 Luog...
莫比乌斯反演+模板
链接https://www.lydsy.com/JudgeOnline/problem.php?id=2301
34-tidytext包学习：主题建模
1、隐含狄利克雷分布LDA 隐含狄利克雷分布LDA(Latent Dirichlet allocation)，是一...
「罗马人的故事11-13」：皇帝尤利安？他也配做皇帝吗？
尤利安（尤利安努斯）克狄乌斯·尤利安与柏提那克斯是两条不同的升迁通道，于公元133年他出生意大利北部的城市，家里...
莫比乌斯反演-从基础开始
提示：别用莫比乌斯反演公式，会炸的只需要记住： [gcd(i,j)=1]=\sum_{d|gcd(i,j)}\m...
POI 2007 ZAP - 莫比乌斯反演
LUOGU 3455DescriptionFGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数和，有多...
狄利克雷卷积的运算律
设都是定义在正整数集合上的函数，他们的狄利克雷卷积是一个定义在同样范围内的函数，用表示，满足：或者写成：...
莫比乌斯反演-2-拓展形式
设的定义域是大于等于 1 的实数。如果，，那么。这被称作是莫比乌斯反演的拓展形式。通过简单的代入演算可以知...

狄利克雷卷积和莫比乌斯反演

积性函数

定义

性质

举例

狄利克雷卷积

定义

性质

卷积关系

莫比乌斯反演

莫比乌斯反演定理

相关文章

狄利克雷卷积和莫比乌斯反演

莫比乌斯变换-1-经典形式与狄利克雷卷积

莫比乌斯反演

莫比乌斯反演+模板

34-tidytext包学习：主题建模

「罗马人的故事11-13」：皇帝尤利安？他也配做皇帝吗？

莫比乌斯反演-从基础开始

POI 2007 ZAP - 莫比乌斯反演

狄利克雷卷积的运算律

莫比乌斯反演-2-拓展形式

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读