积性函数筛法（2）_算法

积性函数前缀和筛法

起因是我正在学筛法，然后去看了一眼最快解。

没想到 P4213 【模板】杜教筛、P3768 简单的数学题、P5325 【模板】Min_25 筛 的最快解都被同一位大佬 @XeCtera 垄断，且前两篇的他还没有开 $\rm O2$ 优化。

考虑到这是一篇比较近的提交，我猜测其使用了某种科技，打开一看发现是 $\Theta(n^{2/3}\log^{-1}n)$ 的，而且其实现竟然比较简洁，去看这位大佬的个人博客发现其只讲了一种（也很快的）朴素杜教筛写法，却没有关于时间复杂度降低的技巧叙述（upd：原来是没有往下翻太深，求 $\mu$ 的块筛是有特殊优化的）。

去网上搜这种科技发现似乎是这种 看起来很麻烦的筛法。

本篇有很多摘抄和分析自 @XeCtera 的博客及代码，在此感谢。

---

目录

• 前言
• 块筛与杜教筛
  • $\rm Dirichlet$ 双曲线法
  • 块筛
  • 块筛卷积
  • 杜教筛
  • 复杂度分析
  • 实现 & 极致卡常
• 洲阁筛与 $\text {min\_25}$ 筛
  • 思路构造
  • $\rm min\_25$ 筛的搜索实现
• $\text {PN}$ 筛
  • $\text {Powerful Number}$ 及其性质
  • $\rm PN$ 筛的原理
  • 实现
• 复杂度上的进展
  • 算法原理及流程介绍
  • 实现
• 例题
• 参考资料

以下常用 $x/y$ 表示 $\left\lfloor\frac{x}{y}\right\rfloor$（但 $n^{1/3}$ 这种明显的分数表示不是整数除法），用 $[x]$ 表示 $\lfloor x\rfloor$。

本篇的复杂度记号并不严谨，是 $\Theta$ 和 $\cal O$ 混用的，大家意会就好。

函数运算记号出现 $*$ 时认为是 $\rm Dirichlet$ 卷积，剩下的都认为是函数乘法，例如 $id^c(x)=x^c$。

前言

我们常常需要解决积性函数的前缀和问题，对于大多数积性函数可以使用线性筛法 $\Theta(n)$ 求出 $[1,n]$ 处的值，但我们对此并不满足，于是就有了各种积性函数前缀和筛法，本文将由浅入深地介绍常用的筛法。

你可以在本篇笔记中以不那么狭隘的视角认识筛法。

本篇不会有太多的例题，因为是对筛法性质的探索。

块筛与杜教筛

$\rm Dirichlet$ 双曲线法

对于数论函数 $f,g,h:\mathbb Z^+\to \mathbb R,f=g*h$，其中 $\mathbb R$ 为交换环，定义 ${\rm S}f(x)=\sum_{i=1}^xf(i)$，那么有：

$${\rm S}f(x)=\sum_{ab\le x}g(a)h(b)$$

可以引入 $\rm Dirichlet$ 双曲线法对其快速计算：

若 $x,y>0\wedge xy=n$（注意 $x,y$ 可以是实数），则：

$${\rm S}(f*g)(n)=\sum_{ab\le n}f(a)g(b)=\sum_{a\le x}f(a){\rm S}g(n/a)+\sum_{b\le y}g(b){\rm S}f(n/b)-{\rm S} f(x){\rm S}g(y)$$

通常取 $x=y=\sqrt n$。

解释：

我觉得不言而喻了。

上式的等价版本其实是：

$${\rm S}(f*g)(n)=\sum_{ab\le n}f(a)g(b)=\sum_{a\le n}f(a)\sum_{b\le n/a}g(b)=\sum_{a\le n}f(a){\rm S}g(n/a)$$

这种整除分块的形式是我们更熟悉的。

双曲线法只能给我们提供一个行动纲领，想要快速计算 ${\rm S}(f*g)$，我们需要一些更强大的工具。

块筛

并不是一种筛法，而是一个概念。

对于数论函数 $f$，将 $i\in\mathbb N\cap[1,n],{\rm S}f(n/i)$ 的值称为 $f$ 在 $n$ 处的块筛，块筛一共有 $\Theta(\sqrt n)$ 个值，下文称 $f$ 在 $n$ 处的块筛为 ${\rm B}f(n)$。

（事实上可以证明前 $[1,\sqrt n]\cap\mathbb N$ 一定都是块筛的下标，$\frac{n}{i-1} - \frac{n}{i} = \frac{n}{i*(i-1)} > 1$，因此两者的下取整值不同。）

许多算法用到的其实就是块筛的值，最典型的例子就是整除分块，除了多测，其他时候你基本用到的都是块筛。

回顾前文 $\rm Dirichlet$ 双曲线法和整除分块的式子，可以发现，计算其中右式时，我们需要用到的就是 ${\rm B}f,{\rm B}g$。

也就是说，如果我们已知 ${\rm B}f,{\rm B}g$，我们可以 $\Theta(\sqrt n)$ 求出 ${\rm S}(f*g)(n)$ 的值，这个的用处大概就是不需要傻傻地去用杜教筛再来一遍。

块筛卷积

已知 ${\rm B}f,{\rm B}g$，求 ${\rm B}(f*g)$。

直接使用双曲线法（或整除分块）计算就好，复杂度等稍后讲完本质相同的杜教筛再分析。

杜教筛

换个直观点的名称可能应该叫块筛卷积逆/块筛除法？

若 $f*g=h$，已知 ${\rm B}g,{\rm B}h$，如何求 ${\rm B}f$？

$${\rm S}h(n)=\sum_{a\le n}g(a){\rm S}f(n/a)$$

发现 $a=1$ 时整个柿子中出现了 ${\rm S}f(n)$，将其提出来：

$$g(1){\rm S}f(n)={\rm S}h(n)-\sum_{a=2}^ng(a){\rm S}f(n/a)\\{\rm S}f(n)=\frac{{\rm S}h(n)-\sum_{a=2}^ng(a){\rm S}f(n/a)}{g(1)}$$

若 $g$ 为积性函数则 $g(1)=1$，所以这个分母通常当作没有。

在这里顺便给出 $\rm Dirichlet$ 双曲线法求解杜教筛的过程，在下文我将论述 $\rm Dirichlet$ 双曲线法与整除分块的常数差异是巨大的。

令 $s=[\sqrt n]$：

$${\rm S}h(n)=\sum_{a\le s}f(a){\rm S}g(n/a)+\sum_{b\le s}g(b){\rm S}f(n/b)-{\rm S} f(s){\rm S}g(s)$$

发现 $b=1$ 时原式中出现了 ${\rm S} f(n)$，将其提出：

$$\begin{aligned}g(1){\rm S}f(n)&={\rm S}h(n)-\sum_{a\le s}f(a){\rm S}g(n/a)-\sum_{b=2}^sg(b){\rm S}f(n/b)+{\rm S} f(s){\rm S}g(s)\\&=\frac{{\rm S}h(n)-\sum_{a=1}^sf(a){\rm S}g(n/a)-\sum_{b=2}^sg(b){\rm S}f(n/b)+{\rm S} f(s){\rm S}g(s)}{g(1)}\end{aligned}$$

看着麻烦了不少对吧，如果我们仔细观察的话会发现除法变少了，我们稍后再说。

这就是杜教筛的核心柿子，构造易于求块筛（易于求前缀和）的函数 $g,h$ 使得 $f*g=h$，即可快速计算 $f$。

杜教筛除了常见的递归查表写法，还有一种常数较小的递推写法。

根据上面的转移式，我们知道求解 ${\rm S} f(n)$ 需要依赖 ${\rm S}f(n/i)$，于是我们有如下的算法流程：

• 枚举 $k=1,2,\cdots,[\sqrt n]$，求解 ${\rm S}f(k)$（该部分被后来的预处理所替代）。
• 枚举 $k=[\sqrt n],\cdots,2,1$，求解 ${\rm S}f(n/k)$。

来几个实战演习：求 ${\rm B}\mu(n),{\rm B}\varphi(n)$，利用 $\mu*I=\epsilon,\varphi*I=id$ 即可。

如果同时求两个的话，可以先算 ${\rm B}\mu$，再利用 $\varphi=\mu*id$，使用块筛 $\sqrt n$ 求出 ${\rm S}\varphi(n)$。

再来个例子，反演 的过程在最后会补上，题目转化后为：$f(x)=\varphi(x)x^2$，求 ${\rm B}f$。

有意思的一点是：$fh*gh=(f*g)h$，理由如下：

$$\begin{aligned} \\\sum_{d|x}f(d)h(d)g\left(\frac{x}{d}\right)h\left(\frac{x}{d}\right)=h(x)\sum_{d|x}f(d)g\left(\frac x d\right) \end{aligned}$$

所以很自然的，$f*id^2=id^3$。

复杂度分析

块筛卷积与杜教筛的本质是相同的：

$$\displaystyle T(n)=\Theta\left(\sum_{k=1}^{\sqrt n}\sqrt k\right)+\Theta\left(\sum_{k=1}^{\sqrt n}\sqrt{\dfrac nk}\right)=\Theta(n^{\frac34})$$

设阈值 $B\ge \sqrt n$，则 $1\sim B$ 的部分通常可以线性筛预处理，则剩余部分的时间复杂度变为：

$$\displaystyle T(n)=\Theta\left(\sum_{k=1}^{n/B}\sqrt{\dfrac nk}\right)=\Theta\left(\frac{n}{\sqrt B}\right)$$

如果可以线性预处理，那么时间复杂度为 $\Theta(B+\frac{n}{\sqrt B}),B=n^{2/3}$ 时时间复杂度为 $\Theta(n^{2/3})$。

关于空间复杂度，预处理积性函数的空间复杂度并不能压缩，所以很遗憾，与时间复杂度相同都为 $\Theta(n^{2/3})$。

注意，杜教筛写成递归形式但不带记忆化的复杂度是接近 $\Theta(n)$ 的。

需要注意的一点是（在后文会用到），根据双曲线法的公式，若 $f,g$ 的非零项密度的 $\Theta(\log^{-1}n)$ 的，此时不必枚举 $0$ 项，预处理之外的复杂度可以变为极为优秀的 $\Theta(n^{2/3}\log^{-1}n)$。

实现 & 极致卡常

注：在学习算法时，切忌提前进行常数优化，请先保证正确性与本质都理解透彻后，再写一些复杂的小常数写法，否则你会和曾经的作者一样痛不欲生。

关于块筛的存储，有两种方式：

• 把每个块筛的值维护一个大小为 $2\sqrt n$ 的数组，并维护实际下标与数组下标的双射。
• 维护两个数组，一个存储 $[1,\sqrt n]$，另一个存储 $[\sqrt n,n]$，每个转移都拆成三部分，即大对大、大对小、小对小（或者维护一个数组但把大的部分坐标平移一下）。

第一种方式更为好写，第二种方式有更小的常数（因为可以把一部分除法变为乘法），在下方的“卡常”版本中采用了第二种实现方式。

推荐考场上按照第一种方式来，如果有闲情雅致卡常的话再慢慢改成第二种方式。

递归是好写的：

auto DJ=[](auto &&DJ,ll n,auto &mp,auto &&Sf,auto &&Sg,auto &&S)->ll{
    if(n<=B) return Sf[n];
    if(mp.count(n)) return mp[n];
    ll &ans=mp[n]=S(n);
    for(ll l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans-=(Sg(r)-Sg(l-1))*DJ(DJ,n/l,mp,Sf,Sg,S);
    } return ans;
};

递推写法也并不难，预处理省略了（块筛中下标比较大的部分存储下标的倒数即可，方便访问且常数小）：

auto SF=[](ll x) {return x<=B?sf[x]:Sf[n/x];};
UF(i,n/B,1) {
    ll m=n/i;Sf[i]=S(m);
    for(ll l=2,r;l<=m;l=r+1) {
        r=m/(m/l);
        Sf[i]-=(Sg(r)-Sg(l-1))*SF(m/l);
    } 
}

带记忆化的递归 总时间跑了约 3.5s，而 不带记忆化的递推块筛 跑出了惊人的 5.2s。

想必带上记忆化也不会优化太多，但最优解的 @XeCtera 使用 不带记忆化的递推块筛 跑出了 315ms 的好成绩。

经查看，他使用的是双曲线法而非整除分块，难道这两种方法的效率差的很大吗？

我们可以依照 $\rm Dirichlet$ 双曲线法类比着写一份代码，看看速度差异。

（在推导过程中，我仍然觉得整除分块更为直观强大，但是在写代码方面把整除分块换成双曲线无疑会变快不少。）

经过实测，在 P4213 【模板】杜教筛 中，整除分块里 每多一次除法 最后一个点的总时间就会增加 600~800ms，这是相当恐怖的。

令我意外的是，换用双曲线法后，将瓶颈处的整数除法变为“先存倒数再浮点数乘法”竟然是更快的，并直接让我总时间 380ms->280ms，超过了 @XeCtera 的暴力。

注意浮点数乘法写 x+=1.0*y/z 效率不如 x+=int(1.0*y/z)，前者是用 double 算完加法再转回 int，不精确且慢。

于是我们写出了这样一份通用杜教筛板子，且完成了极致卡常：

auto D=[](ll n,auto &f,auto &sf,auto &Sf,auto &&Sg,auto &&g,auto &&Sh) {
    int s=sqrt(n);
    F(i,n/B+1,s) Sf[i]=sf[n/i];
    UF(i,n/B,1) {
        int m=n/i,S=sqrt(m);i=n/m;
        Sf[i]=Sh(m)+sf[S]*Sg(S)-Sg(m);
        F(j,2,S) {
            ll t=i*j,t2=m*inv[j];
            Sf[i]-=(t>s?sf[t2]:Sf[t])*g(j)+Sg(t2)*f[j];
        }
    } return Sf[1];
};// f*g=h,query Sf
auto Q=[](ll n,auto &&f,auto &&sf,auto &&Sf,auto &&g,auto &&Sg){
    int s=sqrt(n);
    ll res=-sf[s]*Sg(s);
    F(i,1,s) res+=f[i]*Sg(n/i)+g(i)*Sf[i];
    return res;
};//f=g*h,query sf[n]

块筛卷积类比着杜教筛写即可。

结尾注：在实际应用中更易操作也常数优秀的写法是开一个数组，前 $S$ 位存储小部分的值，后 $S$ 位存储大数的值，大数的映射规则是 x<->2*S+1-n/x。

洲阁筛与 $\rm min\_25$ 筛

思路构造

由于杜教筛需要你构造易于求块筛（前缀和）的函数 $g,h$，相对来说不是那么友好。

那么我们考虑更加一般的一类积性函数：$\forall p\in\mathbb P, f(p)$ 是一个低次多项式，且 $f(p^c)$ 的值可以快速求出。

用 $f_p$ 表示 $f$ 仅保留 $p$ 的幂处的函数值、剩余值都为 $0$，用 $\prod(*)$ 表示以狄利克雷卷积为乘法的连乘。

首先根据积性函数的性质，原函数 $f$ 等于各素数贡献的 $\rm Dirichlet$ 卷积：

$$f=\prod_{p\in\mathbb P}(*)f_p$$

我们把素数分为 $>\sqrt n$ 的和 $\le \sqrt n$ 的，分别称其为大素数和小素数。

我们想要对一个中间结果 ${\rm B}g$ 附加或取消 ${\rm B}f_p$ 的贡献，根据上面的整除分块公式：

$${\rm S}(f*g)(n)=\sum_{a\le n}f(a){\rm S}g(n/a)$$

由于 $f_p$ 中只有 $\log_p n$ 项有值，我们枚举 $a=p^c$，就可以在 $\Theta(\sqrt n\log_p n)$ 的复杂度内求出新的块筛。

考虑每个数至多有一个大素数因子，我们先考虑所有大素数的贡献 ${\rm B}(\prod(*)_{p\ge \sqrt n}f_p)$，此时只有素数处的值非零，因此我们可以把大素数贡献拆成若干个 $id^c$（将低次多项式拆开）的贡献之和。

我们把 $id^c$ 中的小素数贡献取消掉，然后组合出我们想要的积性函数，就得到了 ${\rm B}(\prod(*)_{p\ge \sqrt n}f_p)$（大素数的贡献）。

再附加上 $f$ 中小素数贡献就可以了，我们之前说过 $f(p^c)$ 可以快速求，所以这部分也是简单的。

这样可以得到一个做法，分析一下复杂度：

$$\displaystyle \sum_{p\le \sqrt n}\mathcal O(\sqrt n\log_pn)=\int_1^{\sqrt n}\mathcal O(\sqrt n\log_pn)\log^{-1}p\,\mathrm{d}p=\mathcal O(n\log^{-1}n)$$

菜！

我们考虑优化这个做法。

如果你取消贡献时从小到大取消，附加贡献从大到小附加，你会发现取消 $f_p$ 的时候 $g$ 中 $\le p^2$ 的位置只有 $1$ 和 $\ge p$ 的质数有值，而根据我们之前的分析，$f(p)$ 处的值是一个朴素的低次多项式，也就是说如果我们直接保留质数处的值，在之后的过程中仍然是可处理的。

也就是说我们整除分块的时候 $a$ 可以从 $p^2$ 开始枚举了，但你发现这好像还是 $\Theta(\sqrt n\log_p n)$ 的啊？？

不一样的地方在于需要算的 $n/x$ 至少要满足 $\ge p^2$，然后就能得出 $x\le \cal O(n/p^2)$，即合法的 $x$ 至多有 $\cal O(n/p^2)$ 个。

重新分析一下复杂度，以 $p=n^{1/4}$ 为界限（注意是以这个为界限分析，代码中不需要区分）：

$$\cal \sum_{p\le n^{1/4}}O(\sqrt n\log_pn)+\sum_{n^{1/4}< p\le \sqrt n}O\left(\frac{n}{p^2}\log_pn\right)=O(n^{3/4}\log^{-1}n)$$

这就是大名鼎鼎的洲阁筛，用 $\cal O(n^{3/4}\log^{-1} n)$ 的时间复杂度和 $\Theta(\sqrt n)$ 的空间复杂度求解几乎任意会遇到的积性函数。

（网络上关于洲阁筛和 $\rm min\_25$ 筛的讲解几乎是清一色的 $\rm dp$，在笔者看来这并不直观，所以本篇采用了另一种角度来引入，虽然在实现上还是得老老实实基于 $\rm dp$。）

洲阁筛的实现

关于最初始的 ${\rm B}id^c$，只能委屈我们用自然数幂和公式来求了，记不住伯努利数就打个高斯消元凑合一下吧。

不要指望洲阁筛有很优秀的写法，当我们决定在一个积性函数上保留质数处的值时，它已经暂时不是一个积性函数了，做法自然也称不上优美。

关于取消和附加贡献的部分，我们需要做一个魔改版的 $\rm Dirichlet$ 卷积（逆卷积），所以肯定不能一个数一个数地取消了，每次要把一个质数幂次集来附加或取消。

正常的跑卷积如果在原来的数组，需要类似于跑 $0/1$ 背包的方式倒序附加。

而倘若是 $f_p(p^k)=(p^k)^c$ 这种特殊的形式，那我们就开心了，我们可以直接对该质数跑一个类似完全背包的东西，正序附加，这样一次处理完整个质数幂。

我们发现第一次取消 $id^c(p^k)$ 时便是这种形式，而第二次附加就是普通函数了。

我们来讨论一些具体细节：

• 最开始的时候我们需要默认每个 $id^c(1)=0$，这是因为我们在取消贡献时少了 $1$ 处的值就可以自然地少减掉一个 $p$，达到保留这个质数的目的。
• 下面附加贡献的形式上我们需要采用 $\text{dp}$，因为魔改后的数组其实并没有太好的性质，所以我们要粗暴一点来理解它。
  • 注意：我们此处仍然粗暴地将 $1$ 处的值视为 $0$，这是因为若干个 $id^c$ 组合之后 $1$ 处的值是混乱的，而我们上一步基于 $id^c(1)=0$。
  • 设 $h_{i,x}$ 为 $[1,x]$ 中与 $\prod_{j<i}p_i$ 互质的下标的 $f$ 的和（由于不是完全积性函数，我们枚举的是最小质因子），则转移为：

$$h_{i,x}\gets h_{i+1,x}+\sum_{c>0}f(p_{i}^c)h_{i+1,x/p_i^c}（有误）$$

• • 但是！这描述的是把质数位置也删掉的方程。
  • 若考虑上我们保留的质数位置，方程应该长这样：

$$\begin{aligned}h_{i,x}&\gets h_{{i+1,x}}+\sum_{\substack{c>0\\p_i^{c}\le x}}f(p_{i}^c)([c>1]+h_{i+1,x/p_i^c}- [x/p_i^c\ge p_i]h_{i+1,p_i})\\&=h_{i+1,x}+\sum_{\substack{c>0\\p_i^{c+1}\le x}}(f(p_i^{c+1})+f(p_i^c)(h_{i+1,x/p_i^c}-h_{i+1,p_i}))\end{aligned}$$

大体思路就是你要获得这个位置上的真实值，就必须减掉没有贡献的质数们，我们倒序加入质数，所以此时的 $h_{i+1,p_i}$​ 就是我们要减掉的。

为什么有 $[c>1]$ 呢，因为你把这个质数的值保留了下来，但质数的次幂没有保留（我们把 $1$ 处的值抠掉就是为了保证统计质数时不会由 $1$ 转移而来造成重复贡献，但质数的次幂并没有被保留，它理应通过 $1$ 转移而来，这就是这个系数的来源。）

这步推导基于若 $x\in[p^c,p^{c+1})$，则 $h_{i+1,x/p_i^c}=0$（仅能组成 $1$，而 $1$ 处的值并无贡献），所以把两个柿子拆开。

在真实实现上还是可以比这个破 $\rm dp$ 优美一点点的，可以写在一个一维数组里。

以 P5325 【模板】Min_25 筛 为例，我们需要求 ${\rm B}f,f(p^k)=p^{2k}-p^k$，$n\le 10^{10}$。

代码。

$\rm min\_25$ 筛的搜索实现

$\rm min\_25$ 筛通过搜索实现洲阁筛的思想，成功在小数据下暴打了一众筛法。

其实就是把比较复杂的第二部分写成搜索而已，需要提前处理质数的 $id^c$ 前缀和。

虽然它的常数很小，但由于其第二部分没有采用优化，实质上复杂度是 $\cal O(n^{1-\epsilon})$ 的，在范围比较大的时候打不过洲阁筛。

并且它只能求单点值，不是块筛很难打得过洲阁筛。

代码等有空了写。

$\text {PN}$ 筛

$\text {Powerful Number}$ 及其性质

我们称每个质因子的幂次都 $\ge 2$ 的数为 $\text{Powerful Number}$，我喜欢把其构成的集合记作 $\mathbb{PN}$（懒得打）。

性质：$|\mathbb{PN}\cap[1,n]|=\mathcal O(\sqrt n)$。

显然 $x=a^2b^3\iff x\in\mathbb{PN}$，考虑把每个奇数次质因子扔三个到 $b$ 里，剩下的和偶数次的扔到 $a$ 里，枚举 $a$ 可得：

$$\begin{aligned}&\mathcal O\left(\sum_{a=1}^{\sqrt n}\left(\frac n{a^2}\right)^{\frac 1 3}\right)\\=\ &\mathcal O\left(\int_1^{\sqrt n}\left(\frac n{x^2}\right)^{\frac 1 3}\text{d}x\right)\\=\ &\mathcal O(\sqrt n)\\\end{aligned}$$

求出 $\mathbb{PN}\cap[1,n]$ 只需要暴力搜索质因数组合即可。

$\rm PN$ 筛的原理

这是一种对杜教筛的扩展，可以在杜教筛的 $\Theta(n^{2/3})$ 复杂度内求出一些复杂积性函数的块筛。

设我们要求 ${\rm B}f$，我们需要找到一个积性函数 $g$ 满足 $g$ 在 $p\in \mathbb P$ 处的值与 $f$ 都相同。

设 $h=f*g^{-*}$（$g*h=f$），由于 $\rm Dirichlet$ 卷积及其逆运算关于积性函数是封闭的，可知 $h$ 也是积性函数。

那么由于 $\forall p\in\mathbb P,f(p)=g(p)h(1)+g(1)h(p),h(1)=g(1)=1$，可得 $h(1)=1,h(p)=0$。

由于 $h$ 是积性函数，所以只有在 $x\in\mathbb{PN}$ 处 $h(x)$ 有可能不为 $0$。

想一想之前的整除分块式子：

$${\rm S}f(n)=\sum_{i\in[1,n]\cap\mathbb{PN}}h(i){\rm S}g(n/i)$$

放下 ${\rm S}g(n/i)$ 不管，我们还需要求出 $h(x)(x\in\mathbb{PN})$。

由于积性函数，其实质就是要求 $h(p^c),p\in\mathbb P$。

如何通用地计算 $h(p^c)$ 呢？

考虑 $f(p^c)=\sum_{d=0}^ch(p^{d})g(p^{c-d})$，移项得 $h(p^c)=f(p^c)-\sum_{d=0}^{c-1}h(p^d)g(p^{c-d})$。

这确实是个极为通用的方法，复杂度为 $\Theta(\frac{\sqrt n}{\ln n}\log^2_p n)$，可以运用上文的分析方法分析为 $\cal O(\sqrt n)$ 的。

（可能是 $\Theta(\frac{\sqrt n}{\ln n})$ 的，但我们至少要加上 $\mathbb {PN}$ 的个数。）

综上，若 ${\rm S}g$ 容易计算，则该算法单点复杂度为 $\Theta(\sqrt n)$，否则使用杜教筛求解，单点和块筛复杂度都变为与杜教筛相同的 $\Theta(n^{2/3})$。

实现

以 P5325 【模板】Min_25 筛 为例，我们找的 $g$ 可以是 $i\varphi(i)$。

code，需要特别注意的一点是，枚举 $\rm PN$ 时最好设定一个 $lim=[n/x]$，不要贸然乘上 $x*p_i^2$，这会爆 long long。

复杂度上的进展

我们终于可以开始介绍开头提到的那个时间复杂度 $\cal O(n^{2/3}\log^{-1}n)$ 的简单筛法了。

它其实是对杜教筛的扩展，结合了一部分洲阁筛的思想，可以让 $\rm PN$ 筛和杜教筛包括块筛卷积的复杂度变为原来的 $\frac{1}{\log n}$。

算法原理及流程介绍

现在有一个可以杜教筛的函数 $f$，我们要在 $\cal O(n^{2/3}\log^{-1}n)$ 的复杂度内求出其块筛。

考虑以 $n^{1/6}$ 为界，若我们把 $[1,n^{1/6} ]\cap \mathbb P$ 的小素数贡献从全局暴力取消掉，则复杂度为：

$$\sum_{i=1}^{n^{1/6}}[i\in\mathbb P]\cal O(\sqrt n\log_i n)=O(n^{2/3}\log^{-1} n)$$

这个 $\log^{-1}n$ 是质数密度，而我们的 $\log_p n$ 为什么可以相当于常数呢？

你其实也能感受到，其实只有常数个 $\log_p n$ 是 $\log_2 n$ 的级别，剩下大部分 $\log_p n$ 其实都是常数级别，感性理解是这样，证明的话可以随便放缩一下，不是本文重点。

然后你就惊奇地发现，所有函数的非零值密度都变成了 $\cal O(\log^{-1} n)$（证明可以见 zzt’s blog），此时双曲线法、杜教筛、块筛卷积的复杂度都变为原来的 $\frac{1}{\log n}$。

由于我们可以轻易地加回小素数贡献，那你此时先考虑把不含小素数因子的部分算出。

再次考虑以 $n^{2/3}$ 为界，你发现 $[1,n^{2/3}]$ 的有效值部分共 $\cal O(n^{2/3}\log^{-1} n)$ 个，所以这部分可以直接爆搜质因子组成（注意不要搜小素数），直接求出其函数值。

然后再考虑 $(n^{2/3},n]$ 的部分，由于 $f$ 可杜教筛，直接开筛，复杂度分析同带预处理的杜教筛，只不过这次我们要精细实现，观察双曲线法的公式：

$${\rm S}(f*g)(n)=\sum_{a\le \sqrt n}f(a){\rm S}g(n/a)+\sum_{b\le \sqrt n}g(b){\rm S}f(n/b)-{\rm S} f(\sqrt n){\rm S}g(\sqrt n)$$

你求的是不含小素数因子的部分，所以要注意辅助函数 $g,h$ 也要去掉小素数贡献，所以 $a,b$ 只需要枚举有值部分即可，直接用一个数组记录下来哪些位置没有被撤销就好。

最后加回小素数贡献即可。

值得注意的是，该算法空间复杂度是 $\Theta(n^{2/3})$（因为枚举质因子需要用到 $\Theta(n^{2/3})$ 以内的素数），但其实可以优化到 $\Theta(\sqrt n)$。

你发现 $>n^{1/2}$ 的质数根本不用枚举，因为该数不用小素数能组合出来的在 $n^{2/3}$ 以内的数只有它自己，而它自己是可以用 $id^c$ 凑出来的。

以 $\mu$ 为例，我们在筛其他素数的时候故意加上一个 $1$，然后把块筛和 ${\rm B}I$ 减掉小素数的贡献相减，这样所有 $[1,n^{2/3}]$ 的值就处理好了，且只用到了 $\Theta(\sqrt n)$ 的空间，再也不怕出题人给一个 $10^{12}$ 杜教筛板子卡你空间了。

由于 ${\rm B}I$ 本来就是筛 $\mu$ 要用到的，所以没什么多余要写的，需要注意尽管 $\mu=0$ 也要继续 dfs，因为最后要加上 $1$。

嘶。写出来是写出来了，就是有点慢，杜教模板跑的没直接杜教暴力快。

看来拆分成两个数组还是有很大的常数优化的。

这个方法可以看作是杜教筛的一个优化空间小技巧吧，其实最开始写这篇就是奔着这个做法来的，没想到惨淡收场，不过中间还是收获了不少的。

参考资料

OI中常用数论函数求和法的简化陈述

OI 积性函数求和现有做法的最后一块拼图

浅谈数论函数求和法：杜教筛

积性函数求和问题的一种筛法

后记