关于莫比乌斯函数的前缀和
  • 板块学术版
  • 楼主toolazy
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/23 17:06
  • 上次更新2024/7/23 18:46:09
查看原帖
关于莫比乌斯函数的前缀和
1033727
toolazy楼主2024/7/23 17:06

μ\mu 的前缀和人人都会求,不会左转独脚筛(

而 μ2\mu^2(不是复合,只是平方乘积)的前缀和依旧人人都会求,不会左转完全平方数(

接下来的问题是 μ2⋅id3\mu^2\cdot\text{id}^3(不是复合只是乘积)的前缀和能做吗?

此问题来源于做 LOJ #6222. 幂数!(加强版) 时我最后导出来的式子:

count=∑i=1⌊n3⌋μ2(i)⋅S0(⌊ni3⌋)sum=∑i=1⌊n3⌋μ2(i)⋅i3⋅S2(⌊ni3⌋)Sk(n)=∑i=1nik\text{count}=\sum_{i=1}^{\lfloor\sqrt[3] n\rfloor}\mu^2(i)\cdot S^0\bigg(\bigg\lfloor\sqrt\frac n{i^3}\bigg\rfloor\bigg)\\ \text{sum}=\sum_{i=1}^{\lfloor\sqrt[3]n\rfloor}\mu^2(i)\cdot i^3\cdot S^2\bigg(\bigg\lfloor\sqrt\frac n{i^3}\bigg\rfloor\bigg)\\ S^k(n)=\sum_{i=1}^ni^k

先抛开这个式子能不能做不说,我想问这个东西能不能独脚筛前缀和。

搜索无果,还望各位大佬帮帮忙。

2024/7/23 17:06
加载中...