杜教筛小结

发表于 2018-04-15

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

具体是这样：找到两个函数$g,s$,使得$g* f=s$,并且可以快速算出g和s的前缀和，其中$g$满足$g(1)=1$ 设$F(n)=\sum_{i=1}^n f(i)$,$G(n)=\sum_{i=1}^ng(i),S(n)=\sum_{i=1}^ns(i)$。由于$g(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)$，就不需要哈希表了。

板子


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