首页 > 代码库 > 最高科技——疯狂的前缀和
最高科技——疯狂的前缀和
求\[\sum_{k=1}^N f_k\]
显然这玩意是可以\(O(N)\)的,看起来也不能再优化了。
但是在这个宇宙中确实还存在着更快的算法……
令\[g_n=\sum_{d|n}f_d , F_n=\sum_{k=1}^{n}f_k\]
因为\[\sum_{k=1}^N g_k = \sum_{k=1}^N {f_k \lfloor \frac Nk \rfloor} = \sum_{k=1}^N F_{\lfloor \frac Nk \rfloor}\]
整理得到\[F_N=\sum_{k=1}^N g_k - \sum_{k=2}^N F_{\lfloor \frac Nk \rfloor}\]
如果能够在 \(O(\sqrt{N})\)的时间内求出\(\sum_{k=1}^N g_k\),那么可以在\(O(N^\frac 34)\)的时间内计算出\(F(N)\)。
\(\sum_{k=1}^N g_k\)对于某些特殊的\(g_k\)能做的很快,例如\[\sum_{k=1}^N\sum_{d|k}\mu(d)=1\]\[\sum_{k=1}^N \sum_{d|k}\phi(d)=\sum_{k=1}^N k=\frac{N(N+1)}{2}\]
如果\(g_n\)能够很快的计算,那么可以对于\(n \leq N^\frac 23\)线性暴力计算\(F_n\),否则递归计算,可以做到\(O(N^\frac 23)\)。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。