Prutekoi's blog

定义

若数论函数$f$满足对任意$i,j$互质,满足$f(i*j)=f(i)*f(j)$,则称f为积性函数。
特别的,若对任意$i,j$都满足$f(i*j)=f(i)*f(j)$,则称$f$为完全积性函数。

常见积性函数

$e(n)=[n==1]$

$1(n)=1$

$id(n)=n$

$id^k(n)=n^k$

$\mu(n)$

$\varphi(n)$

$d(n)=\sum_{i|n}1$

$\sigma(n)=\sum_{i|n}i$

前四个是完全积性函数,后四个是数论积性函数。

狄利克雷卷积

$\mu*1=e$

$\varphi*1=id$

$\mu*id=\varphi$

$(\varphi\cdot id^k)*id^k=id^{k+1}$

因为对于每个 $f(1)\not = 0$ 的函数都有逆元，我们可以直接 $O(n\log n)$ 递推得到一个函数的逆，具体的是考虑贡献，因为 $n$ 以内的狄利克雷卷积的计算次数是约数个数和即 $O(n\log n)$，我们只要把这些都精准枚举到即可。

性质和算法

积性函数的逆元也是积性函数。
两个积性函数的乘积或狄利克雷卷积还是积性函数。
对于积性函数,只要探究出$f(p^k)$的表达式,即可以用欧拉线性筛线性求出。
杜教筛。咕咕咕

一些奇怪的公式

$d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$

证明(来自洛谷题解):

我们考虑把每个因子一一映射。
如果$ij$的因子中有一个因子$p^c$,$i$中有因子$p^a$,$j$中有因子$p^b$。我们规定:

• 如果$c\leqslant a$,那么在$i$中选择。
• 如果$c>a$,那么我们把$c$减去$a$,在$j$中选择$p^{c-a}$(在$j$中选择$p^e$表示的是$p^{a+e}$)
  对于$ij$的因子$k$的其他因子同理。于是对于任何一个$k$有一个唯一的映射,且每一个选择对应着唯一的k。
  通过如上过程,我们发现:对于$ij$的因子$k=\prod p_i^{c_i}$,我们不可能同时在$i$和$j$中选择$p_i$（优先在$i$ 中选择，如果不够就只在$j$中选择不够的指数），故$x$和$y$必须互质。
  等式得证。

$\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}$

$\mu(ij)=\mu(i)\mu(j)[gcd(i,j)=1]$