杜教筛(+贝尔级数+powerful number)
command_block
2019-04-05 18:58:19
开坑终于开到这里了,先庆贺一下。
**前置知识** ： 狄利克雷克雷卷积与数论函数。
可见 [莫比乌斯反演与数论函数](https://www.luogu.org/blog/command-block/mu-bi-wu-si-fan-yan-ji-ji-ying-yong) （附 ： 文章比较古老，可能过时）
符号约定:
- $S_F(n)=\sum\limits_{i=1}^nF(i)$,即前缀和。
- $p$ 一般表示质数。
- 涉及的积性函数均有 $F(1)=1$。
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------------
# ${\mathscr P}\!art\ 1$ : 杜教筛
## 一般化推导
- **从卷积开始**
杜教筛用于求数论函数的前缀和，利用的是迪利克雷卷积的性质。
假设我们有一个狄利克雷卷积式子 $A*B=C$。欲求 $S_A(N)$。
( 注意大写 $N$ 和小写 $n$ 的区别 )
写出 $S_C(n)=\sum\limits_{i=1}^nC(i)$
$=\sum\limits_{i=1}^n\sum\limits_{d|i}B(d)A(i/d)$
$=\sum\limits_{d=1}^nB(d)\sum\limits_{d|i}^{n}A(i/d)$
$=\sum\limits_{d=1}^nB(d)\sum\limits_{i=1}^{\lfloor n/d\rfloor}A(i)$
$=\sum\limits_{d=1}^nB(d)S_A(\lfloor n/d\rfloor)$
将 $S_A(n)$ 移项（注意 $B(1)=1$），整理得 ：
$S_A(n)=S_C(n)-\sum\limits_{d=2}^nB(d)S_A(\lfloor n/d\rfloor)$
怎么快速计算这个式子呢？
- **优化&复杂度分析**
这是个递归式，先**假设我们已知右侧的所有量**（可以 $O(1)$ 任意取用），只考虑求和的复杂度。
可以使用整除分块，求解一次的复杂度为 $O(\sqrt{n})$。
考虑问题中涉及到的本质不同的 $S_A(n)$ 有多少个。
- **整除定理①** ： $\big\lfloor\lfloor n/a\rfloor/b\big\rfloor=\lfloor n/(ab)\rfloor$
**推论** ： $N$ 无论经历多少次整除，所得均 $\in \big\{\lfloor N/k\rfloor \big\}$。
- **整除定理②** ： $\big\{r\Big|\lfloor n/r\rfloor≠\lfloor n/(r-1)\rfloor\big\}=\big\{\lfloor n/k\rfloor\big\}$
人话 ： 整除分块中的边界恰是由 $\lfloor n/k\rfloor$ 产生的。
**证明** ： 考虑 $r=\big\lfloor n/\lfloor n/r\rfloor\big\rfloor$。
（这两个定理是学习筛法的重要基础）
$S_A(n)$ 中的参数 $n$ 都是由 $N$ 整除得来的，有 $O(\sqrt{N})$ 个。
取 $\lfloor N/i\rfloor$ 中最大的 $\sqrt{N}$ 个对整除分块的复杂度求和。
复杂度为 $O\bigg(\sum\limits_{i=1}^{\sqrt{N}}\sqrt{N/i}\bigg)=O(N^{3/4})$ （需要积分）
这个复杂度还不够好，考虑使用线性筛预处理 $T$ 以内的 $S(n)$。
这样，若 $N/i\leq T$ 的就不需要求了，可以推出 $i<N/T$ 才对复杂度有贡献。
复杂度为 $O\bigg(T+\sum\limits_{i=1}^{N/T}\sqrt{N/i}\bigg)=O(T+nT^{-1/2})$。
令 $T=nT^{-1/2}$ 解得 $T=n^{2/3}$ 可得最优复杂度为 $O(n^{2/3})$。
- **原料**
接下来，解决 $B,C$ 函数的求值问题。
$B$ 函数在整除分块中需要求区间和，由定理②，只需要 $\big\{\lfloor N/k\rfloor \big\}$ 处的值。
$C$ 函数的参数和 $A$ 函数的参数是对应的，也只需要 $\big\{\lfloor N/k\rfloor \big\}$ 处的值。
给出一个数论函数 $F$ ,对于给定的 $n$ 和任意 $d$ ,求出 $S_F(\lfloor n/d\rfloor)$ ,称为**块筛**。
显然，只需要对 $B,C$ 完成块筛，即可满足需求。
- **适用性**
假如 $F$ 能在 $O(n^{2/3})$ 内完成块筛,则称之为**可杜教筛**。
不难得出，在 $A*B=C$ 这一卷积式中，如果 $B,C$ 都可可杜教筛, $A$可线筛（存在较为普适的积性函数筛法）,那么 $A$ 也可杜教筛。
此外，已知 $A,B$ 得到 $C$ 也是容易的。式子如下：
$S_C(n)=\sum\limits_{d=1}^nB(d)S_A(\lfloor n/d\rfloor)$
于是，在任意卷积式子中都可以“知二筛一”了。
由此可以发现，杜教筛在经典的知识体系里面是很好用的。
## 一些具体函数的筛法
- **例题①** ： [P4213 【模板】杜教筛（Sum）](https://www.luogu.com.cn/problem/P4213)
常见的数论函数 : 如 $\mu,\varphi$ ，直接求前缀和并没有什么思路，但这些函数都满足一些优美的卷积恒等式。
某种程度上，卷积式也可以看作对函数定义的刻画。
如 $\mu*I=e,\ \ \varphi*I=id$ ,而 $I,e,id$ 都是完全积性函数,其前缀和易求。
- ## $\mu$
卷积式 ： $\mu*I=e$。
套用式子得 $S_{\mu}(n)=S_{e}(n)-\sum\limits_{i=2}^nI(i)S_{\mu}(\lfloor n/i\rfloor)$
即 $S_{\mu}(n)=1-\sum\limits_{i=2}^nS_{\mu}(\lfloor n/i\rfloor)$
- ## $\varphi$
卷积式 ： $\varphi*I=id$。
套用式子得 $S_{\varphi}(n)=S_{id}(n)-\sum\limits_{i=2}^nI(i)S_{\varphi}(\lfloor n/i\rfloor)$
即 $S_{\mu}(n)=\frac{n(n+1)}{2}-\sum\limits_{i=2}^nS_{\varphi}(\lfloor n/i\rfloor)$
- 代码实现注意事项 :
记忆化可以不使用 `map`，记录 $\lfloor n/d\rfloor$ 中的 $d$ 即可。
两个函数一起递归可以减小整初分块的常数。
由于询问较多，预处理略多一些。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define Limit 6000500
using namespace std;
bool e[Limit];
int tn,lim,p[Limit];
ll phi[Limit],mu[Limit];
void getsth()
{
e[1]=1;phi[1]=mu[1]=1;
for (int i=2,t;i<=lim;i++){
if (!e[i]){
p[++tn]=i;
mu[i]=-1;
phi[i]=i-1;
}
for (int j=1;j<=tn&&(t=p[j]*i)<=lim;j++){
e[t]=1;
if (i%p[j]==0){
phi[t]=phi[i]*p[j];
break;
}mu[t]=-mu[i];
phi[t]=phi[i]*(p[j]-1);
}
}
for (int i=2;i<=lim;i++){
mu[i]+=mu[i-1];
phi[i]+=phi[i-1];
}
}
int N;
ll _Smu[2005],_Sphi[2005];
inline ll Smu(int n)
{
if (n<=lim)return mu[n];
return _Smu[N/n];
}
inline ll Sphi(int n)
{
if (n<=lim)return phi[n];
return _Sphi[N/n];
}
void S(int n,int d)
{
if (n<=lim||_Sphi[d])return ;
ll tmu=1,tphi=1ll*n*(n+1)>>1;
int l=2,r;
for (;l<=n;){
r=n/(n/l);
S(n/l,d*l);
tmu-=Smu(n/l)*(r-l+1);
tphi-=Sphi(n/l)*(r-l+1);
l=r+1;
}_Smu[d]=tmu;_Sphi[d]=tphi;
}
int Sn[15];ll Tn;
int main()
{
int T;scanf("%d",&T);
for (int i=1;i<=T;i++){
scanf("%d",&Sn[i]);
Tn+=Sn[i];
}lim=min((int)pow(Tn,0.66)+5,6000000);
getsth();
for (int i=1;i<=T;i++){
N=Sn[i];
memset(_Sphi,0,sizeof(_Sphi));
S(N,1);
printf("%lld %lld\n",Sphi(N),Smu(N));
}return 0;
}
```
- **例题②** : $σ_k$
**定义** ： $σ_k(n)=\sum\limits_{d|n}d^k$ ，即因数的 $k$ 次方和。
易得 $σ_k=I*id_k$。
套用式子得 $\sum\limits_{i=1}^nσ_k(i)=\sum\limits_{i=1}^nid_k(i)S_I(\lfloor n/i\rfloor)$。
即 $\sum\limits_{i=1}^nσ_k(i)=\sum\limits_{i=1}^ni^k\lfloor n/i\rfloor$
整除分块求解， $i^k$ 的部分和是经典的自然数幂和问题。
- 鉴于实际运用中涉及的次数 $k$ 往往很小，下面给出一些常见的自然数幂和 ：
$S_{id}(n)=\frac{n(n+1)}{2}$
$S_{id_2}(n)=\frac{n(n+1)(2n+1)}{6}$
$S_{id_3}(n)=\left[\frac{n(n+1)}{2}\right]^2$
直接整除分块复杂度仍然是 $O(n^{3/4})$ ，同样需要线筛预处理才能做到 $O(n^{2/3})$。
- **例题③** : $\mu·id_k$，$\varphi·id_k$ (点乘)
剥点乘有一个技巧,当 $C$ 是**完全积性函数**时 $(A·C)*(B·C)=(A*B)·C$ (提公因式)
**证明** : $\sum\limits_{d|n}\big(A(d)C(d)\big)\big(B(\frac{n}{d})C(\frac{n}{d})\big)=C(n)\sum\limits_{d|n}A(d)B(\frac{n}{d})$
这里卷上$id_k$得到 :
$(\mu·id_k)*id_k=(\mu·id_k)*(I·id_k)=(\mu*I)·id_k=e$
$(\varphi·id_k)*id_k=(\varphi·id_k)*(I·id_k)=(\varphi*I)·id_k=id_{k+1}$
得到卷积式后杜教筛就是体力活了。
从上述推导中可以看出，从点乘里面剥完全积性函数相对容易。
- **例题④** : $\mu^2*(\mu·id)$
卷上 $id$ 得到 :
$\mu^2*\big((\mu·id)*id\big)=\mu^2*\big((\mu*I)·id\big)=\mu^2*e=\mu^2$
$\mu^2$ 的前缀和是易求的，可见 [[数论记录]P4318 完全平方数](https://www.luogu.com.cn/blog/command-block/post-shuo-lun-ji-lu-p4318-wan-quan-ping-fang-shuo)。
- **例题⑤** : $\mu^2·id_k$
似乎和杜教筛关系不大了……
回忆 ： $\mu^2(n)=\sum\limits_{d^2|n}\mu(d)$。
${\rm Ans}=\sum\limits_{i=1}^n\mu^2(i)*i^k$
$=\sum\limits_{i=1}^ni^k\sum\limits_{d^2|n}\mu(d)$
$=\sum\limits_{d=1}^{\sqrt{n}}\mu(d)\sum\limits_{d^2|i}^ni^k$
$=\sum\limits_{d=1}^{\sqrt{n}}\mu(d)d^{2k}\sum\limits_{i=1}^{\lfloor n/d^2\rfloor}i^k$
后半部分都是自然数幂和能够解决的。根据 $\lfloor n/d^2\rfloor$ 分块。
复杂度和 $\mu^2$ 相同，求单个 $O(n^{1/3})$ ,求块筛 $O(n^{3/5})$。
# ${\mathscr P}\!art\ 2$ : 贝尔级数
## 定义
对于**积性函数** $f(n)$ ,定义其在质数 $p$ 意义下的贝尔级数为:
$$F_p(x)=\sum\limits_{i=0}^{\infty}f(p^i)x^i$$
即在质数 $p$ 及其幂次处观察这个积性函数。
由于相乘转化为了指数相加，所以这个东西就是把**狄利克雷卷积** $\Rightarrow$ **一般多项式卷积**。
- **定理** ： 两个数论函数相狄利克雷卷积，其贝尔级数相乘。
下面给出一些常见的贝尔级数 :
- $e\quad\Rightarrow\quad1$
- $I\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}x^i=\frac{1}{1-x}$
- $id_k\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}p^{ik}x^i=\frac{1}{1-p^kx}$
- $I^{-1}=\mu\quad\Rightarrow\quad \left(\frac{1}{1-x}\right)^{-1}=1-x$
由此可以自然地得出 $\mu$ 的定义式.
- $\mu^2\quad\Rightarrow\quad 1+x$
- $d\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}ix^i=\frac{1}{(1-x)^2}$
可与 $I*I=d$ 互推。
- $σ_k\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}x^i\sum\limits_{j=0}^ip^{jk}=\frac{1}{(1-x)(1-p^kx)}$
可与 $I*id_k=σ_k$ 互推。
- $\varphi\quad\Rightarrow\quad 1+\sum\limits_{i=1}^{\infty}p^{i-1}(p-1)x^i$
$\qquad\qquad\ \ =1+\frac{p-1}{p}(\sum\limits_{i=0}^{\infty}p^{i}x^i-1)$
$\qquad\qquad\ \ =1+\frac{p-1}{p}(\frac{1}{1-px}-1)=\frac{1-x}{1-px}$ , 可与$\varphi*I=id$互推。
- $w(n)=2^\text{n的不同质因子数}$ ,显然有 $w(p^k)=2$
$w\quad\Rightarrow\quad1+\sum\limits_{i=1}^{\infty}2x^i=\frac{1+x}{1-x}$
这能推出 $w=\mu^2*I$
另外,点积对贝尔级数也可以产生影响,一般是点积**完全积性函数**。
点积 $e$ 相当于变成 $e$ ，点积 $I$ 则不变。
点积 $id$ 对函数贝尔级数的影响：把 $x$ 代换成 $p^kx$ ,证明:
- $F·id_k\Longrightarrow \sum\limits_{i=1}^{\infty}F(p^i)p^{ki}x^i=\sum\limits_{i=1}^{\infty}F(p^i)(p^kx)^i$
将 $p^kx$ 看作整体即可。
下面给出一些例子:
- $\mu·id_k\quad\Rightarrow\quad 1-p^kx$
- $\varphi·id_k\quad\Rightarrow\quad \frac{1-p^kx}{1-p^{k+1}x}$
- **杜教筛例题⑤** ： $f(p^k)=p^k+[k>0](-1)^k$
先写出 $f$ 的贝尔级数 ： $F_p(x)=1+\sum\limits_{k=1}\big((-1)^k+p^k\big)=\frac{1}{1+x}+\frac{1}{1-px}-1$
接下来构造卷积，令 $G_p(x)=(1+x)(1-px)$ 可得 $(G*F)_p(x)=(1+x)+(1-px)-(1+x)(1-px)=1+px^2$。
$(i+x)$ 对应 $\mu$，而 $(1-px)$ 对应 $\mu^2·id$，所以 $G$ 正是例题④中的函数。
对于 $1+px^2$ 对应的函数 $h$，满足 $h(n)$ 非 $0$ 的 $n$ 满足所有素因子次数均为 $2$。
也即 $n=d^2$ 且 $\mu^2(d)$。
可得 $S_h(n)=\sum\limits_{d=1}^{\sqrt{n}}i\mu^2(i)$ ，这是易求的。
# ${\mathscr P}\!art\ 3$ : powerful number
$\rm zzq$ 大爷说这是杜教筛的拓展,所以就一起讲了。
**定义** : $\text{powerful number}$ 是 **没有 $\bf 1$ 次质因子** 的数。也简称为 $\rm PN$。
一个强有力的结论 : $n$ 以内 $\rm PN$ 的个数为 $O(\sqrt{n})$ 。
- **证明** :
所有PN必然可表示成 $a^2b^3$ 的形式,恰好偶数次的素因子塞到 $a$ 里面,奇数次的素因子塞一次 $b$ 。(这构成一个单射)
考虑枚举 $a$ 考虑满足条件的 $b$ 个数,得 $\sum\limits_{a=1}^{\sqrt{n}}(n/a^2)^{1/3}$ ,积分得到 $O(\sqrt{n})$.
- 应用方法 : **拟合法**
**例题①** : [P5325 【模板】Min_25筛](https://www.luogu.com.cn/problem/P5325)
（对你没看错，这玩意可以硬干 Min_25 筛板子）
**题意** : 设 $F(p^k)=p^k(p^k-1)$ ,求 $S_F(n)$
有$F(p)=p(p-1)$ ,构造函数 $G(x)=x\varphi(x)$ ,显然其是积性函数。
而且我们发现 $G(p)=F(p)$ ,这称作**素数拟合**,至于为什么要这么构造后面再讲。
设数论函数 $H(n)$ 满足 $F=G*H$ ,即 $H=F/G$ (狄利克雷卷积除法)。
这里给出几个结论 (相关证明左转 [莫比乌斯反演与数论函数](https://www.luogu.com.cn/blog/command-block/mu-bi-wu-si-fan-yan-ji-ji-ying-yong) ) ：
- 积性函数的逆唯一。
- $F(1)=1$ 的积性函数必有逆。
- 积性函数的逆还是积性函数。
这就保证了 $H$ 的合法性,而且我们可以得到 $H$ 也是积性函数。
观察到 $F=G*H\rightarrow F(p)=G(1)H(p)+G(p)H(1)=H(p)+G(p)$
由于$F(p)=G(p)$,可以得到$H(p)=0$.
又因为积性,所以 $H(n)$ 有值的地方**都是 $\bf PN$**! (这就是拟合的原因)
$\sum\limits_{i=1}^nF(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}H(d)G(\frac{i}{d})$
$=\sum\limits_{d=1}^nH(d)\sum\limits_{d|i}^nG(\frac{i}{d})$
$=\sum\limits_{d=1}^nH(d)S_G(\lfloor n/d\rfloor)$
$=\sum\limits_{d=1}^n[d∈PN]H(d)S_G(\lfloor n/d\rfloor)$
我们对 $G$ 进行块筛,然后 $O(\sqrt{n})$ 筛出 $\rm PN$ ,并求出对应的 $H(d)$ 就好了。
这里 $G(n)=x\varphi(x)$ ,明显可以杜教筛,剩下的问题就是求出 $O(\sqrt{n})$ 个 $H(n)$ 了。
首先生成所有的 $\rm PN$ ,方法是 : 枚举 $p^c(c>1;p\leq\sqrt{n})$ ，$dfs$ 搜索即可,这里还顺便得到了分解。
由 $F=G*H$ 可得 $F(p^k)=\sum\limits_{c=0}^kG(p^c)F(p^{k-c})$。
移项得到 $H(p^k)=F(p^k)-\sum\limits_{c=0}^{k-1}H(p^c)*G(p^{k-c})$ (类似多项式求逆)
- 求值复杂度分析
素数密度为 $O(\frac{\sqrt{n}}{\log n})$ ,对于每个素数复杂度为 $O(log_p^2n)$。
这部分复杂度可以估计为 $O\Big(\sum\limits_{i=1}^{\sqrt{n}}\log_i^2n/\log n\Big)=O\Big(\sum\limits_{i=1}^{\sqrt{n}}\frac{\log^2n}{\log^2i}/\log n\Big)=O\Big(\log n\sum\limits_{i=1}^{\sqrt{n}}\frac{1}{\log^2i}\Big)$
积分不太会积，但是容易说明 $O\Big(\sum\limits_{i=1}^{n}\frac{1}{\log^2i}\Big)=O(\sqrt{n}/\log^2n)$。
当 $i\leq n^{1/3}$(分界是随便取的) 时，显然贡献不超过 $O(n^{1/3})$。
当 $i>n^{1/3}$ 时，有 $O(\log^2i)=O(\log^2n)$ ，则这部分贡献不超过 $O(\sqrt{n}/\log^2n)$。
综上，复杂度为 $O(\sqrt{n}/\log n)$。(可能有细微偏差，反正肯定不超过 $O(\sqrt{n})$)
求出需要的 $H(p_k)$ 之后，再利用积性，不难得到函数值。
算上杜教筛,总的复杂度 $O(n^{2/3})$ ,但还是跑不过Min_25……
```cpp
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
#define MaxS 5660000
using namespace std;
const int
mod=1000000007,
Inv2=500000004,
Inv6=166666668;
int lim,lp,tn,p[MaxS];
ll N,G[MaxS],tH[10005][35];
void sieve()
{
G[1]=1;
for (int i=2;i<=lim;i++){
if (!G[i]){p[++tn]=i;G[i]=i-1;}
for (int j=1;j<=tn&&p[j]*i<=lim;j++){
if (i%p[j]==0)
{G[p[j]*i]=G[i]*p[j];break;}
G[p[j]*i]=G[i]*(p[j]-1);
}G[i]=(G[i-1]+G[i]*i)%mod;
}
for (lp=1;1ll*p[lp]*p[lp]<=N;lp++);
ll tG[35];
for (int i=1;i<=lp;i++){
ll x=1ll*p[i]*p[i],sq=x%mod;
tG[0]=tH[i][0]=1;
tG[1]=1ll*p[i]*(p[i]-1)%mod;
for (int k=2;x<=N;x*=p[i],k++){
tG[k]=tG[k-1]*sq%mod;
tH[i][k]=(x%mod)*(x%mod-1)%mod;
for (int c=0;c<k;c++)
tH[i][k]=(tH[i][k]-tH[i][c]*tG[k-c])%mod;
}
}
}
ll _S[2005];
//(phi.id)*id=id2
ll S(ll n)
{
if (n<=lim)return G[n];
if (_S[N/n])return _S[N/n];
ll sum=0,l=2,r;
for (;l<=n;l=r+1){
r=n/(n/l);
sum=(sum+S(n/l)*((r-l+1)%mod)%mod*((l+r)%mod))%mod;
}sum=mod-sum*Inv2%mod;
ll buf=n%mod; buf=buf*(buf+1)%mod*(buf*2+1)%mod*Inv6;
return _S[N/n]=(buf+sum)%mod;
}
ll ans;
void dfs(ll n,ll num,int t)
{
ans=(ans+num*S(N/n))%mod;
for (int i=t;i<=lp;i++){
if (1ll*p[i]*p[i]>N/n)return ;
int k=2;
for (ll x=1ll*p[i]*p[i];x*n<=N;k++,x*=p[i])
dfs(n*x,num*tH[i][k]%mod,i+1);
}
}
int main()
{
scanf("%lld",&N);
lim=max((int)pow(N,0.675)+5,100);
sieve();dfs(1,1,1);
printf("%lld",(ans+mod)%mod);
return 0;
}
```
- **一般化**
给出一个积性函数 $F(n)$ ,求 $S_F(n)$ 。
构造一个易块筛的积性函数 $G(n)$ ,满足 $G(p)=F(p)$ ,即素数拟合。
接着构造 $H=F/G$ ,不难得到 $H(p)=0$ , $H$ 有值的地方均是 $\rm PN$。
能得到 $S_F(n)=\sum\limits_{d=1}^n[d∈PN]H(d)S_G(\lfloor n/d\rfloor)$
接下来干两件事 : 对于 $G$ 块筛 + 求出 $O(\sqrt{n})$ 个 $H(d)$。
值得注意的是,对于 $F$ 块筛并不是一件困难的事。
使用 $\rm PN$ 求和一次是 $O(\sqrt{n})$ 的，配合线性筛预处理，复杂度分析和杜教筛相同，为 $O(n^{2/3})$。
其实还可以做到 $O(n^{3/5})$。
- **定理** ： 若 $G$ 只在 $\rm PN$ 处有值，那么 $G$ 的块筛只有 $O(n^{1/3})$ 个本质不同的值。
在 $S_G(\lfloor n/i\rfloor)$ 中，若 $i>N^{1/3}$ ，则 $\lfloor n/i\rfloor\leq N^{2/3}$ ，这部分只有 $O(\sqrt{N^{2/3}})=O(N^{1/3})$ 个有值的 $G$ ，前缀和也就只会变化 $O(N^{1/3})$ 次。
若 $i\leq N^{1/3}$ ，显然只有 $O(N^{1/3})$ 个。
$F=G*H\Rightarrow S_F(n)=\sum\limits_{d=1}^nG(d)S_H(\lfloor n/d\rfloor)$
由于只有 $O(n^{1/3})$ 个本质不同的 $S_G$ ，该式计算复杂度可降至 $O(n^{1/3})$。
若线性筛预处理到 $T$ ，复杂度为 $O\Big(T+\sum\limits_{i=1}^{N/t}(N/i)^{1/3}\Big)=O(T+N/T^{2/3})$ ,令 $T=N^{3/5}$ 可得最优复杂度为 $O(N^{3/5})$。
**例题②** : 『奇怪的函数』
**题意** : 有积性函数 $F(p^c)=p^{ck_1}+p^{ck_2}$ ,求 $S_F(n)$ ， $n\leq 10^{12},k_1,k_2\leq 10$。
考虑函数 $G=id_{k_1}*id_{k_2}$ ，显然有 $G(p)=p^{k_1}+p^{k_2}$。
容易通过插值 $O\big((k_1+k_2)\sqrt{n}\big)$ 求出 $id_{k_1},id_{k_2}$ 的块筛。
$G$ 的前缀和 $S_G(n)$ 可以使用杜教筛的经典整除分块方法，复杂度为 $O(\sqrt{n})$。
观察最后转化的式子 $S_F(n)=\sum\limits_{d=1}^n[d∈PN]H(d)S_G(\lfloor n/d\rfloor)$
对于每个 $\rm PN$ 整除分块计算对应的 $S_G(n)$ ，复杂度为 $O\Big(\sum\limits_{a,b}\sqrt{n/a^2b^3}\Big)=O\Big(\sum\limits_{a}\sqrt{n}/a\Big)=O(\sqrt{n}\log n)$。
## 综合应用 ：冷群筛
通过前面的讨论，我们已经得到如下的结论 :
$B,C$ 可杜教筛（大多数情况下）对应 $C/B,\ C*B$ 可杜教筛。
我们可以拿已知可筛的函数卷积组合成目标函数来解决问题。
为了方便构造,我们可以预先构造出一些函数。
我们只关心贝尔级数的 $[x^1]$ 项，由于常数项都为 $1$ 两个贝尔级数相乘在 $[x^1]$ 处表现为相加。
前面已经知道如何筛 $\mu·id_k$ 了，即 $1-p^kx$，现在我们可以单点 $-1$。
接下来看看如何单点加一，不难发现 $id_{k}(p)=p^k$ 即可满足要求。
下面来解决一个经典的问题 : $\rm Min_25$ 筛问题。
**题意** : 对于一个积性函数 $F(n)$ ,满足 $F(p)$ 是关于 $p$ 的 $m$ 次多项式（ $m$ 较小 ）, $F(p^k)$ 能快速计算,求 $F$ 的块筛。
考虑利用 $\rm PN$:
构造一个易于块筛的积性函数 $G(n)$ ,满足 $G(p)=F(p)$ ,即素数拟合。
根据 $\rm PN$ 的经典结论,我们只需要得到 $G$ 的块筛,就能够在 $O(n^{3/5})$ 的时间内转化为 $F$ 的块筛。
构造 $G(p)=F(p)$ 相当于钦定了 $G$ 的贝尔级数的 $[x^1]$ 项。
设 $F(p)=\sum\limits_{i=0}^mc[i]p^i$ ，即题面中的低次多项式。
利用卷积，我们可以在某个 $[x^1p^c]$ 处 $±1$。
使用加法倍增即可,需要 $O(m\log S)$ 次杜教筛,比Min_25不知慢到哪里去了Orz。
不过大多数时候,出题人的函数比较有“数论意义(?)”,这个 $c$ 大部分都是 $±1$ ,此时就是 $O(m)$ 次杜教筛,效率还是可以的。
这估计也论证了杜教筛是不可能打过Min_25筛这种毒瘤东西的……
upd : 这种筛法投到UOJ群的时候突然冷群了,被命名为"冷群筛"/kel