F. 牛牛的数论

691 浏览 0 回复 2020-08-29

DQ9911

+关注

知乎有看到过相关的东西今天才想起来
链接
直接枚举powerful number $x$ ，然后算贡献 $\displaystyle\sum_{i=1}^{n/x} i^k$
这里我采用的是伯努利数求自然幂级数，总复杂度为 $O(k^2+n^{\frac 1 2}+kn^{\frac 1 4})$

评论加载中...