杜教筛学习小计

本文主要是介绍杜教筛学习小计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天做模拟赛由于不会杜教筛导致70分。。。
于是去学了一下

$\mu$

求$M(n)=\sum_{i=1}^n\mu(i)$
$\mu$有性质：$\sum_{d|n}\mu(d)=[n=1]$
于是有式子：

$$1=\sum_{i=1}^n[i=1]=\sum_{i=1}^n\sum_{d|i}\mu(d)=\sum_{t=1}^n\sum_{d=1}^{[\frac{n}{t}]}\mu(d)=\sum_{i=1}^nM([\frac{n}{i}])$$
转换一下得到：
$$M(n)=1-\sum_{i=2}^nM([\frac{n}{i}])$$
然后M(n)里n的取值只有根号种，可以递归或者递推算

$\phi$

求$S(n)=\sum_{i=1}^n\phi(i)$
$\phi$有性质：$\sum_{d|n}\phi(d)=n$
（因为相当于枚举gcd，然后$\phi(d)$就是n以内的数跟n的gcd为d的个数）
于是有：

$$\frac{1}{2}\times n\times(n+1)=\sum_{i=1}^ni=\sum_{i=1}^n\sum_{d|n}\phi(d)=\sum_{t=1}^n\sum_{d=1}^{[\frac{n}{t}]}\phi(d)=\sum_{i=1}^nS([\frac{n}{i}])$$
转化一下得到：
$$S(n)=\frac{1}{2}\times n\times(n+1)-\sum_{i=2}^nS([\frac{n}{i}])$$
也可以直接算

这篇关于杜教筛学习小计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---