正解:莫比乌斯反演/欧拉函数
解题报告:
一步非常显然的变形,原式=$\sum_{d=1,d\in prim}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==d]$
后面那个就莫比乌斯反演入门题辣$QwQ$?
就变成$\sum_{p=1}^{n}[p\mbox{为质数}]\sum_{d=1}^{n/p}\mu(d)\lfloor \frac {n/p}{d}\rfloor^2$
十分套路的,后面显然可以数论分块,就变成了$\sum_{p=1}^{n}[p\mbox{为质数}] cal(\lfloor\frac{n}{p}\rfloor)$
于是前面就也能数论分块?考虑再前缀和一个质数个数.然后把前面也数论分块.
也就做两次数论分块,然后复杂度是$O(n)$的$QwQ$
$over$!
然后另一个方法其实$easy$蛮多$QwQ$
你考虑到化出的第一个式子去,显然能想到变形成$\sum_{d=1,d\in prim}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,j)==1]$
看到后面这个,联想到欧拉函数,发现$\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,j)==1]$的答案其实也就$\lfloor\frac{n}{d}\rfloor$内的欧拉函数前缀和乘二减一?(乘二是因为交换顺序嘛,减一是因为算重了$(1,1)$这一对嘛$QwQ$
就$easy$些$QwQ$
代码可以去看加强版
随机推荐
-
[LeetCode] Trapping Rain Water II 收集雨水之二
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevati ...
-
android edittext 去边框 去下划线
EditText的background属性设置为@null就搞定了:android:background="@null"style属性倒是可加可不加 附原文:@SlumberMac ...
-
cas的http配置和rmi远程调用
1.cas配置http请求(服务端) 1) 解压cas-server-3.4.4-release.zip将modules目录下的cas-server-webapp-3.4.4.war改名称为cas.w ...
-
<; java.util >;-- Iterator接口
每一个集合都有自己的数据结构,都有特定的取出自己内部元素的方式.为了便于操作所有的容器,取出元素.将容器内部的取出方式按照一个统一的规则向外提供,这个规则就是Iterator接口. 也就说,只要通过该 ...
-
HDU 1465 不容易系列之一(错排，递归)
简而言之,就是把n个信封全部装错的可能数.(中问题,具体看题目) //当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示, //那么M(n-1)就表示n-1个编号元素放在 ...
-
JavaScript入门(3)
一.认识DOM 文档对象模型DOM(Document Object Model)定义访问和处理HTML文档的标准方法.DOM将HTML文档呈现为带有元素.属性和文本的树结构(节点树). Eg: 将HT ...
-
textarea 的最大高度以及最小高度
<script type="text/javascript"> $(function(){ $("#textarea3").textareaAuto ...
-
关于 AutomationProperties.Name 的一些总结
在 XAML 代码中,我们偶尔会看到 AutomationProperies 的代码,如 AutomationProperties.Name="xxxxx", Automation ...
-
Android 高仿微信朋友圈动态， 支持双击手势放大并滑动查看图片。
转载请注明出处:http://blog.csdn.net/sk719887916/article/details/40348873 作者skay: 最近参与了开发一款旅行APP,其中包含实时聊天和动态 ...
-
iOS UI进阶-3.0 核心动画
Core Animation是一组非常强大的动画处理API,使用它能做出非常炫丽的动画效果,而且往往是事半功倍,使用它需要先添加QuartzCore.framework和引入对应的框架<Quar ...