更新于 2026/7/9 10:51:12 作者

command_block

开坑终于开到这里了,先庆贺一下。

前置知识 ： 狄利克雷克雷卷积与数论函数。

可见 莫比乌斯反演与数论函数 （附 ： 文章比较古老，可能过时）

符号约定:

• $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）

常见的数论函数 : 如 $\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$ 即可。

两个函数一起递归可以减小整初分块的常数。

由于询问较多，预处理略多一些。

#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 完全平方数。

• 例题⑤ : $\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筛

（对你没看错，这玩意可以硬干 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$ (狄利克雷卷积除法)。

这里给出几个结论 (相关证明左转 莫比乌斯反演与数论函数 ) ：

• 积性函数的逆唯一。

• $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……

#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