狄利克雷卷积

φ:欧拉函数,μ:莫比乌斯函数

一、定义:(f*g)(n)=Σd|nf(d)g(n/d)

  例如:(f*g)(6)=f(1)*g(6)+f(2)*g(3)+f(3)*g(2)+f(6)*g(1)

二、性质:

  1.交换律:f*g=g*f

  2.结合律:(f*g)*h=f*(g*h)

  3.分配率:(f+g)*h=f*h+g*h

三、三个等式:

  1.μ*I=ε    注:I(n)=1,ε(n)=[n=1],(只有当n=1时,ε(1)=1;其余都等于0)

  2.φ*I=id     注:id(n)=n

  3.μ*id=φ

  例:(μ*id)(6)=μ(1)*id(6)+μ(2)*id(3)+μ(3)*id(2)+μ(6)*id(1)=1*6-1*3-1*2+1=2=φ(6).

原文地址:https://www.cnblogs.com/liumengliang/p/12623485.html