狄利克雷卷积总结

2024-02-02 03:38

文章标签 总结卷积狄利克

本文主要是介绍狄利克雷卷积总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

狄利克雷卷积

约定

$\ n=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}}$

$\ a \mid b$ ： $\ a$ 整除 $\ b$

$\ a \nmid b$ ： $\ a$ 不整除 $\ b$

$\ a^{k} \parallel b$ ： $\ a^{k} \mid b$ 且 $\ a^{k+1} \nmid b$

$\ (a,b)$ 最大公约数

$\ [a,b]$ 最小公倍数

定义

$\sum_{d \mid n} f(n) g(\frac{n}{d})=\sum_{d_{1} d_{2} =n} f(d_{1})g(d_{2})$

也可写作：

$\circ g$

这相当于一种运算。

性质

结合律

$\circ g) \circ h=f \circ(g \circ h)$

证明

$\begin{array}{crl} & &\,\,\,\,\,\,\,(f \circ g) \circ h\\& &=\sum_{d_{1} \mid n}\{ \sum_{d_{2} \mid d_{1}}f(d_{2})g(\frac{d_{1}}{d_{2}})\} g(\frac{n}{d_{1}}) \\\,\\ & &=\sum_{d_{1} d_{2} d_{3}= n} (f(d_{1})g(d_{2}))g(d_{3}) \\\,\\ & &=\sum_{d_{1} d_{2} d_{3}= n} f(d_{1})(g(d_{2})g(d_{3}))\\\,\\ & &=f \circ(g \circ h)\\\,\\ \end{array}$
证毕

交换律

$\circ g=g \circ f$

证明

$\circ g=\sum_{d_{1} d_{2} =n} f(d_{1})g(d_{2})=\sum_{d_{1} d_{2} =n} g(d_{1})f(d_{2})=g \circ f$

证毕

逆元

对于 $\ f$ 存在 $\ g$ 使
$\circ g = \epsilon(n)$
其中
$\epsilon(n)= [n=1]$
证明

$g(n)=\frac{1}{f(1)} \left( \left[ n=1 \right] - \sum_{i \mid n,i \neq n}f(i) g(\frac{n}{i}) \right)$

如此一来

$\sum_{d \mid n}f(d)g(\frac{n}{d})=f(1)g(n)-\sum_{d \mid n,d \neq 1}f(d)g(\frac{n}{d})=\left[ n=1 \right]$

证毕

分配率

$\circ (g + h)=f \circ g+f \circ h$

证明

$\circ (g + h)=\sum_{d_{1} d_{2} =n} f(d_{1})(g(d_{2})+h(d_{2}))=\sum_{d_{1} d_{2} =n} f(d_{1})g(d_{2})+\sum_{d_{1} d_{2} =n} f(d_{1})h(d_{2})=f \circ g+f \circ h$

数乘结合律

$\cdot f) \circ g=s \cdot (f \circ g)$

证明

$\cdot f) \circ g=\sum_{d_{1} d_{2} =n} (s\cdot f(d_{1}))g(d_{2})=s\sum_{d_{1} d_{2} =n}f(d_{1})g(d_{2})$

证毕

积性的传递性

若 $\ f(n),g(n)$ 为积性 $\ h=f \circ g$ 也是积性的

$\begin{array}{rcl} & &\,\,\,\,\,\,\,h(nm)\\\,\\ & &=\sum_{d \mid nm} f(d) g(\frac{nm}{d}) \\\,\\ & &=\sum_{a \mid n,b \mid m} f(ab)g(\frac{nm}{ab}) \\\,\\ & &=\sum_{a \mid n,b \mid m} f(a)g(\frac{n}{a}) f(b)g(\frac{m}{b}) \\\,\\ & &=\{ \sum_{a \mid n} f(a)g(\frac{n}{a}) \}\{ \sum_{b \mid m} f(b)g(\frac{m}{b}) \} \\\,\\ & &=h(n)h(m) \end{array}$

证毕

$\ f$ 积性则 $f^{-1}$ 积性

证明

设 $\ nm>1$ 时有 $\ n'm' < nm,g(n'm')=g(n')g(m')$ 成立
$\ f(n)$ 的逆元 $\ g(n)=\frac{1}{f(1)} \left( \left[ n=1 \right] - \sum_{i \mid n,i \neq n}f(i) g(\frac{n}{i}) \right)$
$\begin{array}{rcl} & &\,\,\,\,\,\,\,g(nm) \\\,\\ & &=- \sum_{d \mid nm,d \neq 1}f(d)g(\frac{nm}{d}) \\\,\\ & &=- \sum_{a \mid n,b \mid m,ab \neq 1} f(ab) g(\frac{nm}{ab}) \\\,\\ & &=f(1)f(1)g(n)g(m)- \sum_{a \mid n,b \mid m,ab \neq 1} f(a) f(b) g(\frac{n}{a}) g(\frac{m}{b}) \\\,\\ & &=g(n)g(m)- \{ \sum_{a \mid n,a \neq 1} f(a) g(\frac{n}{a}) \} \{ \sum_{b \mid m,b \neq 1} f(b) g(\frac{m}{b}) \}\\\,\\ & &=g(n)g(m)-\epsilon(n) \epsilon(m) \\\,\\ & &=g(n)g(m) \end{array}$

证毕

应用

我们总可以证明求一个狄利克雷卷积的复杂度是 $\ O(n \ln n)$ 的。

这篇关于狄利克雷卷积总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

狄利克雷卷积总结

狄利克雷卷积

约定