杜教筛小结

杜教筛是用来解决这样一个问题的:给定一个积性函数f(x)f(x),求i=1nf(i)\sum_{i=1}^nf(i)

具体是这样: 找到两个积性函数g,sg,s,使得gf=sg* f=s,并且可以快速算出g和s的前缀和. F(n)=i=1nf(i)F(n)=\sum_{i=1}^n f(i),G(n)=i=1ng(i),S(n)=i=1ns(i)G(n)=\sum_{i=1}^ng(i),S(n)=\sum_{i=1}^ns(i)。 由于积性函数的积性,除了全0的函数以外,对于任何积性函数f都有f(1)=1f(1)=1 那么由dnf(d)g(nd)=s(n)\sum_{d|n}f(d)g(\frac{n}{d})=s(n),可以得到

然后就可以展开公式了

然后按照ni\lfloor \frac{n}{i}\rfloor整除分段,递归下去。

算完以后存进一个哈希表(或者STL::tr1::unordered_map之类的东西)里面。

(我也不知道怎么证明出来的)复杂度为O(n34)O(n^{\frac{3}{4}}).

(同样我也不知道怎么证明出来的)如果先预处理出 ,则复杂度变为O(nk+k)O(\frac{n}{\sqrt{k}}+k) (其中k是筛法的复杂度)当k=n23k=n^{\frac{2}{3}}时取得最优值O(n23)O(n^\frac{2}{3})

如果只需要算一个F(n)F(n),那么我们还有一个优化:因为所有需要计算到的F(x)F(x)都能表示成ny\lfloor\frac{n}{y}\rfloor并且yny\le \sqrt{n}(这个就是因为如果y>ny>\sqrt{n}那么xnx\le \sqrt{n}就不会算到了。 于是就可以记录a(x)a(x)表示F(nx)F(\lfloor\frac{n}{x}\rfloor),就不需要哈希表了。

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include<tr1/unordered_map>
ll S(ll x){return /*S(x)*/;}
ll G(ll x){return /*G(x)*/;}
tr1::unordered_map<ll,ll> mp;
ll F(ll x){
if(x<=m)return sF[x]; //sF[x]为F(x)
if(mp.count(x))return mp[x];
ll ans=S(x);
for(ll l=2,r;l<=x;l=r+1){
r=x/(x/l);
ans=(ans-(G(r)-G(l-1))*F(x/r));
}
return mp[x]=ans;
}

举2个栗子:

f=φf=\varphi,则可以构造出g=1,s=Idg=1,s=Id

f=μf=\mu,则可以构造出g=1,s=eg=1,s=e

文章目录
  1. 1. 板子
  2. 2. 举2个栗子:
|

博客使用Disqus作为评论系统