=== === 这里放传送门
=== ===
题解 首先题目给出的A函数实际上就是 1n∑i=1nn?i(i,n)=∑i=1ni(i,n)
然后F函数就可以写成 ∑i=1n∑j=1ij(i,j)
然后按照常用套路化一波式子就会变成 ∑d=1n∑i=1?nd?∑j=1i[(i,j)==1]j 这个样子，后面那一块可以发现就是1..i中与i互质的数字的和，那就是 φ(n)?n+[n==1]2 了。然后可以发现在 d 从1到n枚举的过程中总共有n次i==1的情况，也就是一共有n次加上了 [n==1] 这个条件。那么把这个n提出来，然后把那个除以2也刨掉先不看，式子就变成了 ∑d=1n∑i=1?nd?φ(i)?i 这个样子了。
这个式子显然看起来非常美好哇因为如果设 F(n)=φ(n)?n ，只要能够求出F函数的前缀和就可以枚举除法根n分块了哇
然后又是杜教筛的问题了。。。
现在的问题变成了要求 ∑i=1nφ(n)?n ，用杜教筛。
首先要通过卷积构造一个等式 H=F×G ，其中 H 和 G 都是好求前缀和的函数。于是我们令 H=F×id=∑d|nφ(d)?d?(nd) 。选择id函数的原因就是它能够约掉那个d，然后就变成了 n?∑d|nφ(d) 。后面那一坨是 φ×1 ，也是个 id ，那就变成了 n?n ，也就是 H(n)=n2 。
然后就是按照杜教筛的方法画柿子。。
Sum(n)=∑i=1ni2?∑d|i,d 然后因为i必须是d的倍数但i不能等于d，也就是 id不能等于1。那么枚举 id就变成了：
∑i=1ni2?∑id=2n∑d=1?n?id??F(d)?id
然后设 i′=id，替换一下就有：
∑i=1ni2?∑i=2n∑d=1?ni?F(d)?did=∑i=1ni2?∑i=2ni∑d=1?ni?F(d)
【[51nod1227]平均最小公倍数（莫比乌斯反演+杜教筛）】那么后面就又出现了一段F函数的前缀和的形式， i 的前缀和还有 i2 的前缀和都很好算，于是就可以用杜教筛解决这个问题了。
代码
#include
推荐阅读
