在 \(\mathcal O(n^{1-\epsilon})\) 复杂度内计算积性函数前缀和的算法，处理大概 \(10^{10}\) 级别的数据。
这东西从去年咕到了今年。
以下内容默认 \(p\in \text{prime}\)。
min_25 筛要求积性函数 \(f(p^k)\) 可表示成 \(p\) 低阶多项式，例如 模板题 P5325 中 \(f(p^k)=p^k(p^k-1)\)。
基本思路
min_25 筛基本思路是把答案拆成质数和非质数两部分来分别计算。
第一部分
以 模板题 P5325 为例，拆开 \(f(p^k)=p^{2k}-p^k\)，分别计算。
第一部分要余出来的是 \(g(n,i),sp(x)\)。
设 \(sp(x)\) 为前 \(x\) 个质数的函数值之和，可直接预处理。
设 \(g(n,i)=\sum_{j=2}^n[j\in \text{prime}\lor \operatorname{minp}(j)>p_i]j^k\)，其中 \(\operatorname{minp}(x)\) 表示 \(x\) 最小质因子。
可以发现 \(g(n,i)\) 是完全积性函数，并且在质数处的取值和 \(f(x)\) 一样。
然后递推 \(g(n,i)\)： \[ g(n,i)=g(n,i-1)-p_i^k\Big(g(\lfloor\frac{n}{p_i}\rfloor,i-1)-g(p_{i-1},i-1)\Big) \] 后面就是提出一个 \(p_i^k\) 的质因子，因为是积性函数，所以不用提全。\(g(p_{i-1},i-1)\) 其实就是前 \(i-1\) 个质数的函数值之和。
这东西状态量多大呢？
从第一维看，根据定理 \(\displaystyle \Big\lfloor\frac{\lfloor\frac{n}{a}\rfloor}{b}\Big\rfloor=\lfloor\frac{n}{ab}\rfloor\)，所以只要计算所有 \(\lfloor\frac{n}{x}\rfloor\) 的取值，可以除法分块，是 \(\mathcal O(\sqrt{n})\) 的；
从第二维看，由于非质数中大于 \(\sqrt n\) 的质因数一定不是最小质因子，那么当 \(p_i>\sqrt{n}\) 时，\(g(n,i)=g(n,i-1)\)，所以我们只需要 \(\ge \sqrt{n}\) 的质数，大概 \(10^4\) 规模。
这一部分复杂度 \(\displaystyle \mathcal O(\frac{n^{\frac{2}{3}}}{\log n})\)，并不会证。
实现有个细节，就是第一维的下标是 \(10^{10}\) 级别的存不下（这里用 map/unordered_map 就没什么优势了），但是可以根号分治：\(\lfloor\frac{n}{x}\rfloor\le \sqrt{n}\) 的存一个数组，\(\lfloor\frac{n}{x}\rfloor> \sqrt{n}\) 的按 \(x\) 存另一个数组。
第二部分
该开始统计答案了，设 \(S(n,i)=\sum_{j=2}^n[\operatorname{minp}(j)>p_i]f(j)\)，最后要求的就是 \(S(n,0)\)。
还是一样的思路，设 \(x\) 为最后一个小于等于 \(\sqrt{n}\) 的质数的下标。 \[ S(n,i)=g(n,x)-sp(i)+\sum_{k>i,p_k^c\le n}f(p_k^c)\Big(S(\lfloor\frac{n}{p_k^c}\rfloor,k)+[c\neq 1]\Big) \] 前面就是质数的贡献；后面是合数，因为不是完全积性了，所以得把质因子提全；另外 \([c\neq 1]\) 是把质数的幂算上。
这里不用记忆化，据说复杂度是 \(\mathcal O(n^{1-\epsilon})\)，常数很小。
代码实现
P5325 code：
1 | const int N = 1e6 + 9; |
一些题目
咕。