杜教筛

来源

内容总结自

https://acfcacfca.blog.luogu.org/dls-tql(AcF's Blog)

常规做法

杜教筛用于解决求$S(n)=\sum\limits_{i=1}^nf(i)$的问题

有一种常规做法:

找一个数论函数$g$,

我们要求的是$S(n)$,

$\sum\limits_{i=1}^n (f*g)i=g(1)S(n)+\sum\limits_{d=2}^n g(d)S(\frac{n}{d})$

$g(1)S(n)=\sum\limits_{i=1}^n (f*g)i-\sum\limits_{d=2}^n g(d)S(\frac{n}{d})$

只要能找到可以快速求$\sum\limits_{i=1}^n(f*g)i$和$g$的前缀和的$g$即可。

例子

实现

1
2
3
4
5
6
7
8
9
ll calc(int n){
ll ans=sum_f_g//算f*g前缀和
for(ll l=2;r<=n;l=r+1){
r=n/(n/l);
ans-=(sum_g(r)-sum_g(l-1))*calc(n/l);
//sum_g用于算g的前缀和
}
return ans;
}

可以先筛出前$n^{\frac{2}{3}}$个答案

复杂度为$O(n^{\frac{2}{3}})$

可以使用$hash$记忆化来有化复杂度

avatar
contest0211

  1. 1. 来源
  2. 2. 常规做法
  3. 3. 例子
  4. 4. 实现