杜教筛(+贝尔级数+powerful number)

command_block · 2019-04-05 18:58:19 · 算法·理论

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

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

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

符号约定:

涉及的积性函数均有 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。
（这两个定理是学习筛法的重要基础）
取 $\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 函数的求值问题。
$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*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·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)

- $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。

对于 $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 (狄利克雷卷积除法)。

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

积性函数的逆唯一。
积性函数的逆还是积性函数。

这就保证了 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} 的块筛。

观察最后转化的式子 $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)。

综合应用：冷群筛

通过前面的讨论，我们已经得到如下的结论 :

我们可以拿已知可筛的函数卷积组合成目标函数来解决问题。为了方便构造,我们可以预先构造出一些函数。我们只关心贝尔级数的 $[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