自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:31:08，当前版本为作者最后更新于2021-05-04 16:52:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里给出一个 $\mathcal O(\frac{n^{3/4}}{\log n})$ 解法。

由整除分块结论，对正整数 $n$，有 $|\{\lfloor\frac ni\rfloor:i\in\mathbb Z^+\}|\in O(\sqrt n)$。定义函数 $r:\mathbb Z^+\rightarrow\text{\#}$ 关于 $n$ 的 块筛 为 $r$ 在 $\{\lfloor\frac ni\rfloor:i\in\mathbb Z^+\}$ 处的值。

定义一个函数 $r(n)$ 的前缀和函数为 $r^S(n)$，其中

$$r^S(n)=\sum_{i=1}^nr(i)$$

函数建立

建立函数 $g:\mathbb Z^+\rightarrow\mathbb Z/p\mathbb Z[x]$，定义 $g(n)=n^kx^{f(n)\bmod4}$。我们本质想求 $g$ 关于 $n$ 的块筛。由于 $f(n)$ 为加性函数，$n^k$ 为完全积性函数，$n^kx^{f(n)}$ 为积性函数。于是，在 $\mathbb Z/p\mathbb Z[x]/(x^4-1)$ 环下，$g(n)$ 为积性函数；这里乘法为长度为 $4$ 循环卷积，等价于模 $x^4-1$ 的多项式乘法。

由一些理论，得到 $g(n)\mathbb P(n)$ 的块筛即可 $O(\frac{n^{3/4}}{\log n})$ 得到 $g(n)$ 块筛，其中 $\mathbb P(n)$ 为质数指示函数。注意我们在这里\textbf{无法直接筛}（指 min25 筛）因为不存在完全积性函数可以贯穿 $g(n)$ 在质数处；$n^kx^n$ 和 $n^kx^{n\bmod 4}$ 均不为完全积性函数。

求 $g(n)\mathbb P(n)$ 块筛

定 $g_{\mathbb P}(n)=g(n)\mathbb P(n)$，则如果我们展开 $[x^m]g_{\mathbb P}^S(n)$，其中 $0\le m<4$，发现等价于：

$$\sum_{i=1}^ni^k\mathbb P(i)[i\equiv m\pmod 4]$$

这和 min25 step1 所求的东西基本一致，只多了 $[i\equiv m\pmod 4]$。对 $m=0$，上述值为 $0$；对 $m=2$，上述值为 $[2\le n]2^k$。所以实际有 $[x^1]g_{\mathbb P}^S(n)$ 和 $[x^3]g_{\mathbb P}^S(n)$ 的块筛就可以恢复 $g_\mathbb P(n)$ 的块筛。

考虑广义一下 min25 step1 过程。仍然逐个质数筛。定一个递增变量 $p$，$\mathsf{lpf}(i)$ 为 $i$ 的最小质因子；维护：

$$[x^{m|m\in\{1,3\}}]h_p^S(n)=\sum_{i=1}^ni^k[\mathbb P(i)\lor\mathsf{lpf}(i)>p][i\equiv m\pmod 4] $$

初始，$p=0$，需要初始化这东西：

$$\sum_{i=2}^ni^k[i\equiv m\pmod 4]$$

的块筛，这个可以通过等差数列求和公式找到。我们先看上一个质数 $p'$ 怎么更新到下一个质数 $p$，也就是怎么筛走最小质因子等于 $p$ 的合数。注意当 $p>\sqrt n$ 已经筛走所有合数：最小未筛走合数为 $p^2$，可以停止了。

筛走的合数可以表示为 $px$，其中 $\mathsf{lpf}(x)\ge p\iff\mathsf{lpf}(x)>p'$。$x$ 可以为合数，也可以为大于 $p'$ 的质数。以下开始大力分类讨论。$p$，$px$，与 $x$ 均在模 $4$ 意义表示。

1. 若 $p\equiv 1$，$px\equiv 1$，则 $x\equiv 1$。从 $[x^1]h_p^S(n)$ 筛走 $p^k([x^1]h_{p'}^S(\lfloor\frac np\rfloor)-[x^1]h_{p'}^S(p'))$。
2. 若 $p\equiv 1$，$px\equiv 3$，则 $x\equiv 3$。从 $[x^3]h_p^S(n)$ 筛走 $p^k([x^3]h_{p'}^S(\lfloor\frac np\rfloor)-[x^3]h_{p'}^S(p'))$。
3. 若 $p\equiv 3$，$px\equiv 1$，则 $x\equiv 3$。从 $[x^1]h_p^S(n)$ 筛走 $p^k([x^3]h_{p'}^S(\lfloor\frac np\rfloor)-[x^3]h_{p'}^S(p'))$。
4. 若 $p\equiv 3$，$px\equiv 3$，则 $x\equiv 1$。从 $[x^3]h_p^S(n)$ 筛走 $p^k([x^1]h_{p'}^S(\lfloor\frac np\rfloor)-[x^1]h_{p'}^S(p'))$。

其中所有后者为不该筛走的小于等于 $p'$ 质数，可以预处理。

从 $g(n)\mathbb P(n)$ 块筛得 $g(n)$ 块筛

通常 min25 问题只需要我们对积性函数前缀和单点求值，这时候可以用一个更简洁的 $\mathcal O(n^{1-\varepsilon})$ 递归做法。这里先介绍如何将 min25 step2 扩展到计算前缀和函数块筛。感谢 @GuidingStar 提供这一部分详细讲解。

考虑将合数逐个筛回答案，仍然枚举合数最小质因子 $p=p_m$。先丢走 $g(n)$ 为多项式这性质，定义函数

$$F_m(n)=\sum_{i=2}^ng(n)[\textsf{lpf}(i)\ge p_m\lor i\in\mathbb P] $$

则有边界条件

$$F_{\pi(\sqrt n)+1}(n)=g_{\mathbb P}^S(n)$$

考虑如何筛进最小质因子为 $p_m$ 的合数 $C$。有两个情况：第一 $C$ 包含不为 $C$ 的质因子，也就是 $C=p_m^xC'$ 其中 $\textsf{lpf}(C')>p_m$；或者 $C$ 为 $p_m$ 的幂，也就是 $C=p_m^x$ 其中 $x>1$（注意 $x=1$ 情况已经在质数里包含了！）

枚举 $x$；与上一部分类似推到，第一情况的 $C'$ 从 $1\le x\le\frac{n}{p_m^x}$ 的 $\textsf{lpf}(C')>p_m$ 选，第二情况直接算。由 $g(n)$ 的积性性，第一情况可以直接乘 $g(p_m^x)$ 计算贡献。形式化：

$$F_m(n)=F_{m+1}(n)+\sum_{x=1,p_m^x\le n}g(p_m^x)\max(0,F_{m+1}(\lfloor\frac n{p_m^x}\rfloor)-g_{\mathbb P}^S(p_m))+\sum_{x=2,p_m^x\le n}g(p_m^x) $$

整理一下第一部分发现如果有 $\frac{n}{p_m^x}\ge p_m$，等价于 $p_m^{x+1}\le n$，于是直接枚举 $x+1$ 也没事。

$$F_m(n)=F_{m+1}(n)+\sum_{x=1,p_m^{x+1}\le n}g_m(p_m^x)(F_{m+1}(\lfloor\frac n{p_m^x}\rfloor)-g_{\mathbb P}^S(p_m))+g(p_m^{x+1}) $$

逐 $m$ 地推，从 $\pi(\sqrt n)+1$ 往 $1$，即可。

这里 $F_m(n)$ 值均在环 $\mathbb Z/p\mathbb Z[x]/(x^4-1)$ 操作，乘法为循环卷积。总共时间复杂度 $\mathcal O(\frac{n^{3/4}}{\log n})$。