Dirichlet卷积与杜教筛

循环之美将我带入此坑

1.积性函数与完全积性函数

数论函数:定义域为正整数域,值域为复数域的函数。

积性函数:对于任意一对互质正整数\(p\)、\(q\),有\(f(pq)=f(p)f(q)\)的数论函数。

完全积性函数:对于任意一对正整数\(p\)、\(q\),有\(f(pq)=f(p)f(q)\)的数论函数。

常见的积性函数有:

  • 元函数\(\epsilon(n)=[n=1]\)
  • 恒等函数\(I(n)=1\)
  • 单位函数\(id(n)=n\)
  • 幂函数\(id^k(n)=n^k\)
  • 欧拉函数\(\varphi(n)=\sum_{i=1}^{n}[(n,i)=1]\)
  • 除数函数\(\sigma_k(n)=\sum_{d|n}{d^k}\)
  • 莫比乌斯函数\(\mu(n)=\begin{cases}1&n=1\\(-1)^k&n为k个不同质数之积\\0&其他情况\\\end{cases}\)

其中前四个是完全积性函数。

2.Dirichlet卷积

$$(f*g)(n)=\sum_{d|n}{f(d)g(\frac{n}{d})}$$

显然它满足交换律、结合律,存在单位元\(\epsilon(n)=[n=1]\)。

莫比乌斯函数与恒等函数互为Dirichlet卷积的逆元。

3.杜教筛

有这样一类问题:给定一个积性函数\(f(n)\),求\(F(n)=\sum_{i=1}^{n}f(i)\)。

杜教筛能够在\(O(n^{\frac{2}{3}})\)的时间复杂度内求出一些积性函数的前缀和。

总体思想为,构造一个函数\(g(n)\),那么\((f*g)(n)\)的前缀和可以进行如下变换:

$$\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})=\sum_{ij<=n}f(i)g(j)=\sum_{i=1}^{n}g(i)F(\left\lfloor\frac{n}{i}\right\rfloor)$$

那么有

$$g(1)F(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)F(\left\lfloor\frac{n}{i}\right\rfloor)$$

如果能够快速求出\((f*g)(n)\)和\(g(n)\)的前缀和就能记忆化搜索出\(F(n)\),复杂度\(O(n^\frac{3}{4})\)。如果将\(O(n^\frac{2}{3})\)以内的预处理那么复杂度可以到\(O(n^\frac{2}{3})\)。

很多情况下,\(g\)取恒等函数\(I\)就可以了。比如:

Example.1

求\(F(n)=\sum_{i=1}^{n}\mu(i)\)

根据上面的式子,有

$$F(n)=\sum_{i=1}^{n}\sum_{d|i}\mu(d)-\sum_{i=2}^{n}F(\left\lfloor\frac{n}{i}\right\rfloor)$$

根据莫比乌斯函数的性质

$$F(n)=1-\sum_{i=2}^{n}F(\left\lfloor\frac{n}{i}\right\rfloor)$$

记忆化搜索即可。

Example.2

求\(F(n)=\sum_{i=1}^{n}\varphi(i)\)

$$F(n)=\sum_{i=1}^{n}\sum_{d|i}\varphi(d)-\sum_{i=2}^{n}F(\left\lfloor\frac{n}{i}\right\rfloor)$$

$$F(n)=\frac{n(n+1)}{2}-\sum_{i=2}^{n}F(\left\lfloor\frac{n}{i}\right\rfloor)$$

大同小异

至于复杂的函数还需要具体分析。

说点什么

4 评论 在 "Dirichlet卷积与杜教筛"

提醒
排序:   最新 | 最旧 | 得票最多
游客

评论一番

游客

你们都是数学神犇,太神辣,%%%

游客

orz

成员

好高级的东西啊

wpDiscuz