Dirichlet Convolution

数学题的好东西，很多时候会用它来解题，比如快速判断一个函数是否为积性，很方便。

定义

(f * g)(x) = \sum_{d \mid x} f(d) \cdot g\left(\frac{x}{d}\right)

性质

交换律 / 结合律

f*g = g*h

(f*g)*h = f*(g*h)

通过展开两边的括号来证明

单位元与逆元

\begin{cases} 1 & n = 1 \\ 0 & \text{else} \end{cases}$$ $$f * \varepsilon = \varepsilon * f = f$$ 只要 $f(1) \neq 0$，就有逆元。 $$f^{-1} * f = \varepsilon$$ ## 积性函数 与普通卷积相同。 **若 $f$ 与 $g$ 为积性函数，那么 $f*g$ 也是积性函数。** 证明： 由于 $\gcd(m,n)=1$，任何 $d \mid mn$ 可**唯一**表示为：

d = d_1 d_2, \quad \text{其中 } d_1 \mid m,\ d_2 \mid n,\ \gcd(d_1,d_2)=1

且 $\frac{mn}{d} = \frac{m}{d_1} \cdot \frac{n}{d_2}$

(f * g)(mn) = \sum_{d \mid mn} f(d) , g\left(\frac{mn}{d}\right) = \sum_{d_1 \mid m} \sum_{d_2 \mid n} f(d_1 d_2) , g\left(\frac{m}{d_1} \cdot \frac{n}{d_2}\right)

由于 $f$ 和 $g$ 是积性的，且 $\gcd(d_1,d_2)=1$ 、$\gcd\left(\frac{m}{d_1}, \frac{n}{d_2}\right)=1$，直接替换：

f(d_1 d_2) = f(d_1) f(d_2), \quad g\left(\frac{m}{d_1} \cdot \frac{n}{d_2}\right) = g\left(\frac{m}{d_1}\right) g\left(\frac{n}{d_2}\right)

因此：

(f * g)(mn) = \sum_{d_1 \mid m} \sum_{d_2 \mid n} f(d_1) f(d_2) , g\left(\frac{m}{d_1}\right) g\left(\frac{n}{d_2}\right)

= \left( \sum_{d_1 \mid m} f(d_1) , g\left(\frac{m}{d_1}\right) \right) \left( \sum_{d_2 \mid n} f(d_2) , g\left(\frac{n}{d_2}\right) \right) = (f * g)(m) \cdot (f * g)(n)

Dirichlet Convolution

文章操作

Dirichlet Convolution

定义

性质

交换律 / 结合律

单位元与逆元

相关推荐

评论

Dirichlet Convolution