狄利克雷卷积
定义 狄利克雷卷积： ( f × g ) ( n ) = ∑ d | n f ( d ) ∗ g ( n d ) ( f × g ) ( n ) = ∑ d | n f ( d ) ∗ g ( n d ) 一个例子： f ( x ) = 2 x , g ( x ) = 3 x f ( x ) = 2 x , g ( x ) = 3 x 则 ( f × g ) ( 6 ) = f ( 1 ) g ( 6 ) + f ( 2 ) g ( 3 ) + f ( 3 ) g ( 2 ) + f ( 6 ) g ( 1 ) ( f × g ) ( 6 ) = f ( 1 ) g ( 6 ) + f ( 2 ) g ( 3 ) + f ( 3 ) g ( 2 ) + f ( 6 ) g ( 1 ) 。 往往省略掉 n n 。 狄利克雷卷积定义在 数论函数 上。 数论函数： 如果一个函数的定义域为正整数，值域为复数，则称此函数为数论函数。常见的数论函数有欧拉函数 φ φ 和莫比乌斯函数 μ μ 。 运算律： 1. 结合律 ( f × g ) × h = f × ( g × h ) ( f × g ) × h = f × ( g × h ) 。 2. 交换律 f × g = g × f f × g = g × f 。 3. 加法-狄利克雷卷积分配律 f × ( g + h ) = f × g + f × h f × ( g + h ) = f × g + f × h 。 4. 单位元 单位函数 ϵ ϵ ，使得 f = ϵ × f = f × ϵ f = ϵ × f = f × ϵ 。 单位函数的取值： n = 1 n = 1 时 ϵ ( n ) = 1 ϵ ( n ) = 1 ， n n 取其他值时 ϵ ( n ) = 0 ϵ ( n ) = 0 。 5. 逆元 对于任意数论函数 f f ，如果 f ( 1 ) ≠ 0 f ( 1 ) ≠ 0 ，则存在 唯一 的逆函数 f − 1 f − 1 ，使得 f × f − 1 = ϵ f × f − 1 = ϵ ： 对于 n = 1 n = 1 ，有： f − 1 ( ...