题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5608
这题，看一眼体面就应该知道是杜教筛吧？
唯一的问题就是求\(\sum\limits_{i = 1}^n {{i^2}} \)
然后就不会了，去问问数竞的大爷，被告知：\(\sum\limits_{i = 1}^n {{i^2}} = \frac{{n \cdot (n + 1) \cdot (2n + 1)}}{6}\)是一个基本公式
![FS~3Z]@~(4B0{S~)AKZ2G88](http://oi.cyo.ng/wp-content/uploads/2016/08/FS3Z@4B0SAKZ2G88.jpg)
至于证明，貌似最清真的还是数学归纳法吧：
设i=1,k=2,不难得出此时原式成立
令k’=k+1则有：\(\sum\limits_{i = 1}^{k’} {{i^2} = \sum\limits_{i = 1}^k {{i^2} + {{(k + 1)}^2} = \frac{{(k + 1) \cdot (k + 2) \cdot (2k + 3)}}{6} = \frac{{k’ \cdot (k’ + 1) \cdot (2k’ + 1)}}{6}} } \)
即命题对于\(\forall k\)都成立
Does your site have a contact page? I’m having a tough time locating it but, I’d like to shoot you an email. I’ve got some suggestions for your blog you might be interested in hearing. Either way, great site and I look forward to seeing it grow over time.
When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get three e-mails with the same comment. Is there any way you can remove people from that service? Thank you!
Appreciate you sharing, great blog article.Thanks Again. Awesome.