BZOJ 4916 神犇和蒟蒻

发布于 2017-09-14  204 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4916

题意:求\(\sum_{i=1}^{n}\varphi (i^2)\)


杜教筛练习,太神了不会做啊 T.T 考虑构造函数

$$g(n)=\sum_{i=1}^{n}\varphi (i)\cdot i$$

$$f(n)=\sum_{d|n}^{ }\varphi (d)\cdot n=n^2$$

$$F(n)=\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\varphi (i)\cdot i\cdot \left \lfloor \frac{n}{i} \right \rfloor=\frac{n(n+1)(2n+1)}{6}$$

分块计算过程中是一个等差数列的形式

 

 


一个非常弱的准退役OIER