BZOJ 4916 神犇和蒟蒻


题目链接: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}$$

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

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4916 神犇和蒟蒻


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,