数论卷积相关

逆元，单位元的定义

单位元 \(e\)，也叫做幺元。其在一个半群 \((D, \circ)\)（前一个是元素集合，后一个是运算符）中被定义的话，半群被称作幺半群。

某一个元素 \(x\) 的逆元 \(x^{-1}\)，意思是 \(x \circ x^{-1} = e\)。

例如，
对于 \(\circ = +\)，\(e = 0\)，因此 \(x + x^{-1} = 0\)。
对于 \(\circ = \times\)，\(e = 1\)，因此 \(x \times x^{-1} = 1\)。
对于 \(\circ = \times\)（矩阵乘法），$e = $ 单位矩阵（主对角线是 \(1\) 其他都是 \(0\)）。

Dirichlet 卷积

也叫乘法卷积。
对于两个数列 \(\{a_n\}, \{b_n\}\)，定义 \(\{c_n\}\) 为 \(a,b\) 做狄利克雷卷积的结果。也称 \(c = a * b\)。那么 \(\forall i, c_i = \sum \limits_{k | i} a_k b_{\frac{i}{k}}\)。朴素地进行一次狄利克雷卷积，时间复杂度为 \(O(n \ln n)\)。
性质：
对于两个积性函数 \(f, g\)，\(f*g\) 是积性函数。容易证明。（有什么用？积性函数有一些牛逼的筛法和性质）

在此基础上，定义一些特殊函数。

\(\mathbf 1\) 函数：\(\mathbf 1_x = 1\)，是完全积性函数。

\(e\) 函数：半群 \((f, *)\) 的单位元。考虑其性质：
\(e * f = f\)
当 \(x=1\) 时，\(e_1f_1=1\)，显然 \(e_1=1\)。
当 \(x\neq 1\) 时，\(e_1f_x + e_?f_?... = 1\)，显然 \(e_? = 0\)。
因此 \(e = \{1, 0, 0, ..., 0\}\)。

\(\mu\) 函数：也叫做莫比乌斯函数。是 \(\mathbf 1\) 函数的逆元。也即，\(\mathbf 1 * \mu = e\)
当 \(x=1\) 时，\(\mathbf 1_1 \mu_1 = 1\)，显然 \(\mu_1 = 1\)。
当 \(x=p\) 时，\(\mathbf 1_1 \mu_p + \mathbf 1_p \mu_1 = 0\)，显然 \(\mu_p = -1\)。
为了简便，我们发现可以省去 \(\mathbf 1_?\)。接着看看。
当 \(x=p^k\) 时，\(\mu_1 + \mu_p + \mu_{p^2} + \mu_{p^3} + ...\)，那么当 \(k>1\) 的时候 \(\mu_{p^k} = 0\)。
当 \(x=pq\) 时，$\mu_1 + \mu_p + \mu_{q} + \mu_{pq} $，那么 \(\mu_{pq} = 1\)。
二项式反演得，\(\mu_{p_1p_2p_3...p_k}=(-1)^k\)。
当 \(x=p_1^{a_1}p_2^{a_2}...p_k^{a_k}\) 时，需要 \(\mu_{有平方因子的数}=0\)。
验证一下，确实能对的上。
因此 \(\mu_x = \left\{ \begin{array}{ll} (-1)^k & x 没有平方因子，有 k 个质因数 \\ 0 & x 有平方因子 \end{array} \right. \)

有一个东西是要注意到的。\(\sum \limits_{d | n} f_d\) 等于 \(f *\mathbf 1\)。