首页 > 其他 > 详细

积性函数求和:构造狄利克雷卷积将值域限定于powerful number

时间:2020-04-06 22:37:18      阅读:69      评论:0      收藏:0      [点我收藏+]

前情提要:$O(n^{0.75}/\log n)$ 时间的积性函数求和。当 $n \ge 10^{12}$ 的时候需要十几秒出解。

如果积性函数的性质更好,那么我们可以更快地求和。

假设积性函数 $f$ 和易于求和的积性函数 $g$ 满足 $f(p)=g(p)$,且 $f=g*h$, $g*h$ 表示 $g, h$ 的狄利克雷卷积,也就是 $f(n)=\sum_{d|n}g(d)h\left({n \over d}\right)$.

那么我们函数 $h$ 可能比较难看,但是它具有性质:$h(p)=0$. 这意味着,凡是满足 $h(n) \ne 0$ 的数都是powerful number, 换句话说它的每个素因子次数都不小于 $2$.

Powerful number 可以写成 $a^2b^3$ 的形式。

$\sum_{b=1}^{\sqrt[3]n}\sqrt{n \over b^3}=O\left(\sqrt n\int_{1}^{\sqrt[3]n}t^{-1.5}\mathrm dt\right)=O(\sqrt n)$

所以 powerful number 的个数是 $O(\sqrt n)$.

设 $G$ 是 $g$ 的前缀和。现在我们有:

$$\sum_{i=1}^nf(i)=\sum_{i=1}^n\sum_{j|i}g\left({i \over j}\right)h(j)=\sum_{[j \le n, j\text{ is powerful}]}^nh(j)G\left({n \over j}\right)$$

于是如果我们已经对于所有 powerful number $i$ 求出 $g\left({n \over i}\right)$, 则后续的积性函数求和步骤将在 $O(\sqrt n)$ 时间内完成。

当然 $g$ 的求和可能会比较难做。一些特殊的数论函数可能可以杜教筛求和。比较有意思的是这么一个例子:

题目来源:钟子谦。这是他的 powerful number 求和法博客链接

设积性函数 $f$ 满足 $f(p^c)=2^c$, 求 $\sum_{i=1}^N f(i)$, $N \le 10^{12}$.

注意到 $f(p)=2$, 设 $g(n)$ 表示 $n$ 的约数个数,$g(p)=2=f(p)$. 再构造 $h(p^c)=2^{c-2}(c \ge 2)$, 得 $f=g*h$.

由于 $G(n)=\sum_{i=1}^n\sum_{j|i}1=\sum_{ij \le n}1=2\sum_{i=1}^{\lfloor\sqrt n\rfloor}\left\lfloor{n \over i}\right\rfloor-(\lfloor\sqrt n\rfloor)^2$, 可在 $O(\sqrt n)$ 时间内求 $G(n)$.

所以对于所有 $k={n \over a^2b^3}$ 求 $G(k)$, 时间复杂度为 $O\left(\sum_{a, b}\sqrt{n \over a^2b^3}\right)=O\left(\sum_{a}\sqrt{n \over a^2}\right)=O(\sqrt n\log n)$.

积性函数求和:构造狄利克雷卷积将值域限定于powerful number

原文:https://www.cnblogs.com/nealchen/p/Powerful-Number.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!