数学--数论--积性函数（初步）
一、定义
积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。
二、常见的积性函数
φ(n) －欧拉函数 μ(n) －莫比乌斯函数，关于非平方数的质因子数目 gcd(n,k) －最大公因子，当k固定的情况 d(n) －n的正因子数目 σ(n) －n的所有正因子之和 ε(n) －定义为：若n = 1，ε(n)=1；若 n > 1，ε(n)=0。别称为“对于狄利克雷卷积的乘法单位”（完全积性） λ(n) －刘维尔函数，关于能整除n的质因子的数目
性质 1.若将n表示成质因子分解式
在这里插入图片描述
则有
在这里插入图片描述
2.若f为积性函数且有
在这里插入图片描述
则f为完全积性函数。
特点： 积性函数都可以用线筛处理，就是说复杂度是O(n)。
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-12-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录