数论函数指定义域为正整数集的函数

2.1 数论函数的定义 对于一个数论函数 f ( x ) f(x) f(x) 满足 f ( a b ) = f ( a ) × f ( b ) f(ab) = f(a) × f(b) f(ab)=f(a)×f(b)，则称 f ( x ) f(x) f(x) 为一个积性函数

若 ∀ a , b ∈ Z + ∀ a,b ∈ Z+ ∀a,b∈Z+，都有 f ( a b ) = f ( a ) × f ( b ) f(ab) = f(a) × f(b) f(ab)=f(a)×f(b)，则称 f ( x ) f(x) f(x) 是一个完全积性函数

2.2 积性函数的性质 若 f ( x ) f(x) f(x) 是一个积性函数，且 x x x 的唯一分解式为 x = p 1 c 1 p 2 c 2 … p k c k x= p_1^{c_1} p_2^{c_2}…p_k^{c_k} x=p1c1​​p2c2​​…pkck​​，则 f ( x ) = f(x) = f(x)= ∏ i = 1 k \prod_{i=1}^k ∏i=1k​ f ( p i c i ) f(p_i^{c_i}) f(pici​​)

对于证明，显然每一项之间互质，于是按照积性函数的定义即可证明

注意这个性质是 f(x) 是积性函数的充要条件

设 ϕ ( x ) ϕ(x) ϕ(x) 为在模 x 域下的简化剩余系大小，称为欧拉函数，显然欧拉函数是一个数论函数。并且欧拉函数是一个积性函数。

证明我不会

幺元函数 e ( x ) = [ x = 1 ] e(x) = [x = 1] e(x)=[x=1]我们约定中括号返回一个布尔量，中括号内表达式为真返回1，否则返回0

常函数 o n e ( x ) = 1 one(x) = 1 one(x)=1。不管自变量如何取值函数值恒为 1

标号函数 I d ( x ) = x Id(x) = x Id(x)=x。即返回自变量本身

σ ( k , x ) = ∑ d ∣ x d k σ(k,x) = ∑d∣xdk σ(k,x)=∑d∣xdk

当 k = 1 时，该函数表示 x 的因子之和

当 k = 0 时，该函数表示 x 的因子个数。

当 k 省略时默认为 1

容易证明上面五个函数都是积性函数，除第一个和第五个外都是完全积性函数

暂时略过

设 f f f 和 g g g 都是数论函数，定义 f f f 和 g g g 的狄利克雷卷积为 h，记为 h = f ∗ g h = f∗g h=f∗g

定义 h ( n ) = ∑ x ∗ y = n f ( x ) × g ( y ) h(n) = \sum_{x*y=n}f(x) × g(y) h(n)=∑x∗y=n​f(x)×g(y)

显然狄利克雷卷积拥有交换律和结合律以及乘法对加法的分配律

这里介绍一下单位元

若 f f f 和 g g g 都是积性函数，则 h h h 为积性函数

证明：

若 g ( n ) = ∑ d ∣ n f ( d ) ， 则 g = f ∗ o n e g(n) = \sum_{d∣n} f(d)，则 g = f∗one g(n)=∑d∣n​f(d)，则g=f∗one。其中 o n e one one 为常函数 1

证明上，依照狄利克雷卷积的定义，等价于每一项都乘 1，对答案不产生影响。

这里要注意辨析一下与单位元卷积等于其本身

5.4 常见数论函数的狄利克雷卷积

5.4.1莫比乌斯函数

莫比乌斯函数的性质:

可以改写为

μ μ μ ∗ o n e = e one = e one=e e 为幺元函数

需要指出，积性函数必然存在逆元（因为 f ( 1 ) = 1 f(1) = 1 f(1)=1 ），且逆元仍是积性函数。

对于卷积的第n项可以直接枚举约数，在 n \sqrt n n ​的时间内计算

但是对于狄利克雷卷积的前 n n n项

如果一项一项算的话就需要 n n n\sqrt n nn ​，但实际上可以优化

设 x = d , y = i / d x=d,y=i/d x=d,y=i/d分别枚举 x , y x,y x,y对于 h [ x ∗ y ] + = f [ x ] ∗ g [ y ] h[x*y]+=f[x]*g[y] h[x∗y]+=f[x]∗g[y]即可。 时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)