B_M

数学数学-Dirichlet卷积

数学

Codeforces(5) java课(7) 分治(1) 动态规划(1) 图论(1) 数据结构(2) 算法课(13)

/ 注册

数学-Dirichlet卷积

806 浏览 0 回复 2020-02-17

B_M

+关注

在oi-wiki上学了不少，做一点笔记

积性函数

定义

若对于任意的 $gcd(x,y)==1$ 总有 $f(xy)=f(x)f(y)$ 则函数 $f$ 称为积性函数
若对任意的 $x,y$ ，都有 $f(xy)=f(x)f(y)$ 则函数 $f$ 称为完全积性函数

性质

若 $f(x)$ 和 $g(x)$ 都是积性函数，则 $h(x)=f(x^p)\\ h(x)=f^p(x)\\ h(x)=f(x)g(x)\\ h(x)=\sum_{d|x}f(d)g(\frac{x}{d})$
都是积性函数

举例

单位函数 $\epsilon(x)= \left.\begin{cases}1\quad x=1\\0\quad x\ne1\end{cases}\right.$
恒等函数 $ID(x)=x$ ——x是几就是几
常数函数 $1(x)=1$ ——x是几都是1
欧拉函数 $\phi(x)$ —— $\lt x$ 且与 $x$ 互质的数的个数
莫比乌斯函数 $\mu(x)=\left.\begin{cases}1\quad x=1\\0\quad x的因子中有平方数\\(-1)^k\quad k是x的质因子个数\end{cases}\right.$

Dirichlet卷积

定义

对于两个数论函数 $f(n),g(n)$ 他们的迪利克雷卷积是 $(f*g)(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$ 也就是也就是对于 $i*j==n$ 的整数 $i,j$ 的函数值乘在一起再求和

性质

dirichlet卷积满足结合律和交换律
单位函数 $\epsilon(x)$ 是dirichlet卷积的单位元，任何函数卷上 $\epsilon(x)$ 都是它本身

需要记住的结论

$\epsilon(x)=\sum_{d|n}\mu(d)*1(\frac nd)$
$ID(x)=\sum_{d|n}\phi(d)*1(\frac nd)$
$\phi(x)=\sum_{d|n}ID(d)*\mu(\frac nd)=\sum_{d|n}d\mu(\frac nd)$

一些显然的结论

$x的因子个数=\sum_{d|n}1(d)*1(\frac nd)=\sum_{d|n}1$
$x的因子和=\sum_{d|n}ID(d)*1(\frac nd)=\sum_{d|n}d$

莫比乌斯反演

若对于两个数论函数 $f,g$ 有 $f(n)=\sum_{d|n}g(d)\\$ 则 $g(n)=\sum_{d|n}\mu(d)f(\frac nd)\\$

证明

原式等于： $f(n)=(g*1)(n)\\$
两边同时卷积 $\mu(n)$
$(f\mu)(n)=(g*1*\mu)(n)\\$
因为 $(\mu*1)(n)=\epsilon(n)\\$
所以

$(f\mu)(n)=(g*\epsilon)(n)=g(n)\\$
即 $g(n)=\sum_{d|n}\mu(d)f(\frac nd)\\$

举报

收藏

赞

评论加载中...