题目要求的柿子是：
[large sum_{i=1}^nsum_{j=1}^nsigma(ij)
]
小证明：
(i) 选了的 (j) 就必须在“不选集合”中选择“不选”，(i) 没选的 (j) 的 “不选集合” 中就可选可不选。
这样做显然是一一对应的，而且肯定满足 (i) 的“选集合”和 (j) 的“不选集合”互质。
首先根据结论：
[large
sum_{i=1}^nsum_{j=1}^nsum_{xvert i}sum_{yvert j}[gcd(x,y)=1]dfrac{xj}{y}
]
先枚举 (x,y) ：
[large sum_{x=1}^nsum_{y=1}^nsum_{xvert i}sum_{yvert j}[gcd(x,y)=1]dfrac{xj}{y}
]
把只和 (x,y) 相关的提出来：
[large sum_{x=1}^nsum_{y=1}^n[gcd(x,y)=1]dfrac{x}{y}lfloorfrac nx
floorsum_{yvert j}j
]
把 (varepsilon=I*mu) 换一下：
[large sum_{x=1}^nsum_{y=1}^nsum_{dvert gcd(x,y)}mu(d)dfrac{x}{y}lfloorfrac nx
floorsum_{yvert j}j
]
套路先枚举 (d) ，同时观察到最后那个柿子就是个等差数列：
[large sum_{d=1}^nmu(d)sum_{x=1}^{lfloorfrac nd
floor}sum_{y=1}^{lfloorfrac nd
floor}frac{x}ylfloorfrac n{xd}
floor yddfrac{lfloorfrac {n}{yd}
floor(lfloorfrac {n}{yd}
floor+1)}{2}
]
化简一下：
[large sum_{d=1}^nmu(d)sum_{x=1}^{lfloorfrac nd
floor}sum_{y=1}^{lfloorfrac nd
floor}xdlfloorfrac n{xd}
floor dfrac{lfloorfrac {n}{yd}
floor(lfloorfrac {n}{yd}
floor+1)}{2}
]
把该提出来的提出来：
[large sum_{d=1}^nmu(d)dsum_{x=1}^{lfloorfrac nd
floor}xlfloorfrac n{xd}
floor sum_{y=1}^{lfloorfrac nd
floor}dfrac{lfloorfrac {n}{yd}
floor(lfloorfrac {n}{yd}
floor+1)}{2}
]
接下来可以考虑怎么解决后面两部分，先说最后一个柿子，为了方便，设 (lfloordfrac nd
floor o n) ：
[large sum_{i=1}^nfrac{lfloorfrac{n}{i}
floor(lfloorfrac{n}{i}
floor+1)}{2}
]
把后面的柿子换回等差数列的形式，然后交换求和顺序：
[largesum_{i=1}^nsum_{j=1}^{lfloorfrac ni
floor}j=sum_{j=1}^njsum_{i=1}^{lfloorfrac nj
floor}1=sum_{i=1}^nilfloorfrac ni
floor
]
这时我们再来看前面一个柿子，发现这两个柿子现在不是一样的吗？
那么我们现在只需要解决前面的柿子再平方一下就行了。
还是为了方便，设 (lfloordfrac nd
floor o n) ：
[large sum_{i=1}^nilfloorfrac ni
floor
]
考虑其实际意义：(large ilfloorfrac ni
floor) 的意义就是在 ([1,n]) 当中，(i) 作为因数对其所有倍数的因数和的贡献。
那么对于 ([1,n]) 中所有这样的 (i) ，自然有：
[large sum_{i=1}^nilfloorfrac ni
floor=sum_{i=1}^nsigma_{1}(i)
]
那么现在原式就变成了：
[large Ans=sum_{d=1}^nmu(d)dleft(sum_{i=1}^{leftlfloorfrac n i
ight
floor}sigma_1(i)
ight)^2
]
很容易发现后面的柿子是个整除分块，但是也要计算 (sigma_1) 的前缀和，而前面则是要计算 (mu(d)d) 的前缀和。
考虑杜教筛。
先考虑 (mu(d)d) ，似乎带 (d) 的柿子都可以给它卷个 (id) 使得这个 (d) 被消掉，于是我们试一下：
[large sum_{i=1}^nsum_{dvert i}dcdotmu(frac id)frac id=sum_{i=1}^ni(mu*I)(i)=sum_{i=1}^ni[i=1]=1
]
非常简洁，那么考虑 (id) 的前缀和好求吗？非常好求，就是等差数列，那么我们就可以筛出 (mu(d)d) 了，接下来考虑 (sigma_{1}) ：
想了一万年，发现并没有什么好的函数来筛 (sigma_{1}) ，但是我们发现，其实如果我们直接爆算，那么就是一个除法分块的复杂度（还记得 (large sumlimits_{i=1}^nsigma_{1}(i)=sumlimits_{i=1}^nilfloorfrac ni
floor) 吗）。
但是！这里有个非常高妙的做法：
考虑杜教筛是怎么做到 (O(n^{frac{2}{3}})) 复杂度的：先线性筛出 (n^{frac 23}) 的前缀和，然后剩下的部分除法分块以及递归！
那么我们直接线性筛出这个函数的 (n^{frac23}) ，然后对剩下部分除法分块，复杂度也可以近似为 (n^{frac 23}) ，甚至比杜教筛还要优！（因为还省掉了递归的复杂度，虽然在主定理中这不是瓶颈）
那么就结束了，时间复杂度 (O(n^{frac 23})) 。