【learning】杜教筛求欧拉函数前缀和

　　我们考虑利用\(\sum\limits_{d|n}\varphi(d)=n\)这一性质来处理这个问题

　　设\(f(n)=\sum\limits_{i=1}^{n}\varphi(i)\)

　　那么我们可以得到：
\[
\begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{d|i}\varphi(d)&=\frac{n(n+1)}{2}\\
\end{aligned}
\]
　　所以：
\[
\sum\limits_{i=1}^{n}\sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}\varphi(d)=\sum\limits_{i=1}^{n}f(\lfloor\frac{n}{i}\rfloor)=\frac{n(n+1)}{2}
\]
　　然后我们将\(f(n)\)提出来得到：
\[
f(n)=\frac{n(n+1)}{2}-\sum\limits_{i=2}^{n}f(\lfloor\frac{n}{i}\rfloor)
\]
　　然后就可以对于小于\(\sqrt n\)的前缀和预处理一波，然后再记忆化搜索一下就好了

巴特西

【learning】杜教筛求欧拉函数前缀和

最新文章

热门文章