MCOI R5 F

· · 题解

这里给出一个 \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})。