今年的GDKOI居然考了反演，还要用杜教筛，狠狠的把我骇了一跳， 回来在51nod上随便点开几题看起来像是反演的题，发现都是要用杜教筛（这RP~）， 好吧好吧，那就学杜教筛咯~

杜教筛的套路

有几个大家都很熟悉的式子： $$\sum _{d|n}\mu (d)=[n=1]$$ 根据这个，再写出一个式子： $$\sum _{i=1}^n\sum _{d|i}\mu (d)=1$$ $$\sum _{i=1}^n\sum _{j=1}^{\lfloor \frac{n}{i}\rfloor }\mu (j)=1$$ 那么： $$\sum _{i=1}^n\mu (i)=1-\sum _{i=2}^n\sum _{j=1}^{\lfloor \frac{n}{i}\rfloor }\mu (j)$$ 于是$\mu$的前缀和就可以求了， 其他就是乘了一些奇怪的数也差不多是这样化（见后文）。

记得加上哈希记忆化。 其实并不用哈希， 我们发现，因为我们预处理了至少$\sqrt{n}$个， 所以我们要算的所有的数都是小于$\sqrt{n}$的， 当我们在计算n的答案时，在计算过程中所要访问的所有数x，它的$n/x$的值都是唯一的， 所以我们就直接用$n/x$作为它的哈希值， 计算下一个答案时再清空即可，

关于狄利克雷卷积的先挖坑（逃） #复杂度 杜教筛的复杂度：$O(n^{\frac{2}{3}})$ 然而我并不会证明QwQ 转载唐老师的博客

---

【51nod 1244】莫比乌斯函数之和 求： $$\sum _{i=a}^b\mu (i)$$ 这个直接求出1_b的减去1(a-1)的即可。

#其他例题 例题里面会有杜教筛其他情况的详细讲解（按难度排序） 【51nod 1239】欧拉函数之和 【BZOJ 3944】Sum（双倍经验） 【51nod 1237】最大公约数之和 V3 【51nod 1238】最小公倍数之和 V3 【51NOD 1227】平均最小公倍数（双倍经验）