您的位置: 首页  >  IT文章  >  Dirichlet 卷积学习笔记 Dirichlet 卷积学习笔记

Dirichlet 卷积学习笔记 Dirichlet 卷积学习笔记

分类: IT文章 • 2022-07-06 00:20:32

最近 水痘在家休息，闲得蛋疼 学习了莫比乌斯反演，所以顺便自学一下 Dirichlet 卷积，方便做题。

定义

定义数论函数 (f,g)，则他们的 Dirichlet 卷积为

[(f*g)(x)=sumlimits_{dmid x} f(d)cdot g(frac{x}{d}) ]

同样，

[(f*g)(x)=sumlimits_{dmid x} f(frac{x}{d})cdot g(d) ]

性质

和乘法一样，卷积也有一些性质，证明略：

[f*g=g*f ]

[f*(g+h)=f*g+f*h ]

[(f*g)*h=f*(g*h) ]

我们现在要来看一个非常重要的函数：(varepsilon)，它是这样定义的：

[varepsilon(x)=egin{cases}1&x=1\0&x eq 1end{cases} ]

他有一个性质：任意一个数论函数 (f) 与 (varepsilon) 的卷积都为这个函数本身，即 (f*varepsilon=f)。

这个证明非常简单，但是很有助于加深对 Dirichlet 卷积的理解，证明如下：

[(f*varepsilon)(x)=sumlimits_{dmid x} f(x)cdotvarepsilon(frac{x}{d}) ]

[(f*varepsilon)(x)=f(x)cdotvarepsilon(1)+sumlimits_{dmid x,d eq x} f(x)cdotvarepsilon(frac{x}{d}) ]

由 (varepsilon) 的定义得：

[egin{aligned} (f*varepsilon)(x)=f(x)\ &&square end{aligned}]

更多例子：

我们先定义一些函数：

  • (id(x)=x)
  • (varphi(x)=sumlimits_{i=1}^{x} [gcd(i,x)==1])
  • (1(x)=1)
  • (d(x)=sumlimits_{imid x} 1)
  • (sigma(x)=sumlimits_{imid x} i)
  • 设 (x=prodlimits_{i=1}^c p_i^{k_i})，其中 (p_i) 为质数。

[mu(x)=egin{cases} 1&x=1\(-1)^c&prodlimits_{i=1}^c k_i=1\0& maxlimits_{i=1}^c k_i>1 end{cases}]

那么我们由定义可以得出两个结论，不证明了，都比较简单：

[egin{aligned} d=1*1\sigma=id*1 end{aligned}]

有两个证明较为复杂：

[egin{aligned} varepsilon=1*mu\varphi=id*mu end{aligned}]

其中上面一个属于莫比乌斯函数的内容，之后的博文可能会讲。第二个我们给予证明，伪证如下：

由定义可得，即证：

[sumlimits_{i=1}^{x} [gcd(i,x)==1]=sumlimits_{dmid x} frac{x}{d}cdotmu(d) ]

先考虑 (d=1)，由定义，(mu(1)=1)，因此此时 (frac{x}{d}cdotmu(d)=1)

当 (mu(d)=-1) 时，即 (d) 有奇数个不同的质因子。此时能表示成 (kd) 形式的数有 (frac{x}{d}) 个，这些数都是不与 (x) 互质的，因此要乘以 (-1) 减去。

当 (mu(d)=1,d eq 1) 时，即 (d) 有偶数个不同的质因子。我们考虑两个数 (a,b)，满足 (amid x,bmid x)，(a,b) 都有奇数个不同的质因子。我们在去除 (a) 的倍数和 (b) 的倍数时，很有可能有 (p,q) 满足 (pcdot a=qcdot b)，这个数就被筛掉了两次，我们用容斥原理给它加回来。对于 (a,b) 来说，重复被筛掉的有 (frac{x}{operatorname{lcm}(a,b)}) 个数。我们令 (d=operatorname{lcm}(a,b))。若 (d) 有偶数个不同质因子，我们才考虑，这是因为我们还会有被多加上去的，然后再有多减掉的，如此一直反复直到不存在 (a,b)。我们这里不再考虑三次容斥（其实还是有的），所以我们只需要减去偶数个不同质因子的即可。

由此我们最后得到的就是 (varphi(x))

这个证明不是特别严谨，所以大家不要太当真，这是一个帮助大家理解的证明过程。我也不知道我怎么想出来的。真正的见下。

我们先来证明 (id=varphi*1)

即证：

[x=sumlimits_{dmid x} varphi(d) ]

由于 (varphi) 是一个积性函数，我们只需要证明 (x=p^k) 时满足条件即可。（(p) 为质数）

[egin{aligned} varphi*1&=sumlimits_{dmid x} varphi(frac{x}{d})\&=sumlimits_{i=0}^{k}varphi(p^i)\&= 1+(p-1)cdot p^0+(p-1)cdot p^1+(p-1)cdot p^2+cdots+(p-1)cdot p^{k-1}\&=p^k\&=id end{aligned}]

因此 (id=varphi*1)，由此得：

[egin{aligned} id*mu=varphi*mu*1\id*mu=varphi*varepsilon\id*mu=varphi\&square end{aligned}]

相关推荐