积性函数

概念

数论函数
定义域为正整数的函数称为数论函数。

积性函数
对于数论函数 ，若任意互质的 \(p,q\) 都有 \(f(pq)=f(p)f(q)\)，则称 \(f\) 是积性函数。

完全积性函数
对于数论函数 ，若任意 \(p,q\) 都有 \(f(pq)=f(p)f(q)\) ，则称 \(f\)是完全积性函数

定义逐点加法
\((f+g)(x)=f(x)+g(x)，((f⋅g)(x)=f(x)g(x)\)

定理

积性函数一定满足 \(f(1)=1\)

证明： 显然 \(1\) 与任何数都互质，满足积性函数的定义，那么我们假设存在一个正整数 \(a\) 满足 \(f(a)!=0\)，显然有：\(f(1×a)=f(1)×f(a)\)，两端同除 \(f(a)\) ，得：\(f ( 1 ) = 1\)，性质得证

对于一个大于 1 11的正整数 N ，根据唯一分解定理有\(N=p_1^{c_1}p_2^{c_2}…p_m^{c_m}\)，
则
对于任意积性函数 \(f\) 有： $ f(N) = f(\prod p_i^{a_i}) = \prod f(p_i^{a_i})$

若 \(f\) 完全积性 \(f(N) = \prod f(p_i)^{a_i}\)

由此可得推论：凡是积性函数均可用线性筛法求解

若 \(f(x)\) 和 \(g(x)\) 均为积性函数，则以下函数也为积性函数：

常见积性函数

狄利克雷卷积

原文

原文地址：http://www.cnblogs.com/kingwz/p/16861520.html