积性函数

ycw123 · 2022-03-12 15:30:14 · 个人记录

定义

如果定义在正整数域上的函数 f(n) 满足：

对于互质的 p, q，有 f(pq) = f(p)f(q)

那么我们说 f(n) 是积性函数

特别地，如果 p, q 是任意的，我们说 f(n) 是完全积性函数

常见的积性函数

• 常函数 1(n) = 1
• 单位函数 id(n) = n
• 狄利克雷单位函数 ε(n) = (n == 1)?1 : 0
• 约数和函数 σ(n)，表示 n 的约数之和
• 约数个数函数 d(n)，表示 n 的约数个数
• 欧拉函数 \varphi (n)
• 莫比乌斯函数 μ(n)

积性函数的乘积也是积性函数！