杜教筛小结

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

具体是这样:
找到两个积性函数$g,s$,使得$g* f=s$,并且可以快速算出g和s的前缀和.

设$F(n)=\sum_{i=1}^n f(i)$,$G(n)=\sum_{i=1}^ng(i),S(n)=\sum_{i=1}^ns(i)$。
由于积性函数的积性,除了全0的函数以外,对于任何积性函数f都有$f(1)=1$
那么由$\sum_{d|n}f(d)g(\frac{n}{d})=s(n)$,可以得到$f(n)=s(n)-\sum_{d|n,d\not=n}f(d)g(\frac{n}{d})$

然后就可以展开公式了

$$
\begin{align}
F(n)&=\sum_{i=1}^nf(i)\
&=\sum_{i=1}^n(s(i)-\sum_{j|i,j\not=i}f(j)g(\frac{i}{j}))\
&=S(n)-\sum_{j=1}^n\sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}f(j)g(k)\
&=S(n)-\sum_{k=2}^{n}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}g(k)f(j)\
&=S(n)-\sum_{k=2}^ng(k)F(\lfloor\frac{n}{k}\rfloor)
\end{align
}
$$

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

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

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

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

如果只需要算一个$F(n)$,那么我们还有一个优化:因为所有需要计算到的$F(x)$都能表示成$\lfloor\frac{n}{y}\rfloor$并且$y\le \sqrt{n}$(这个就是因为如果$y>\sqrt{n}$那么$x\le \sqrt{n}$就不会算到了。
于是就可以记录$a(x)$表示$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=\varphi$,则可以构造出$g=1,s=Id$

当$f=\mu$,则可以构造出$g=1,s=e $

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

博客使用Disqus作为评论系统