积性函数

定义

一个数论函数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)$