✕
![preview]()
新鲜事
原文
刚刚刷主页看到一位 acwing 网友求助一道题（只给了截图）。
题面大概是：
给定 $n,k$ 和质数 $p$，记 $f(x)=\sum_{i=1}^x i^k$。
求 $\sum_{S\neq \empty,S\subseteq [n]} f(\gcd(S))$。其中 $\gcd(S)$ 表示 $S$ 中所有元素的 $\gcd$。
输出答案对 $p$ 取模。$n \le 10^9,k\le 10^5,p \le 1.1 \times 10^9$。
但是本人不小心丢失了那个帖子的网址。希望各位神通广大的网友能帮忙找一下。
也欢迎各位在这个帖子下分享做法。
我现在的想法是：先莫比乌斯反演，化简式子，变成 $\sum_{i=1}^n (2^{\lfloor \frac{n}{i} \rfloor}-1) \cdot (f * \mu)(i)$。先 $O(n)$ 预处理所有 $f(i),\mu(i)$，然后做两遍整除分块，时空复杂度都是 $O(n)$。
希望大家能分享更好的做法。
