C - 加权约数和

$$\sum_{i=1}^n\sum_{j=1}^n\max(i,j)\sigma(i*j)\\ =2*\sum_{i=1}^ni*\sum_{j=1}^i\sigma(i*j)-\sum_{i=1}^ni*\sigma(i*i)\\ =2*\sum_{i=1}^nf(i)-\sum_{i=1}^ng(i)$$
下面分别考虑$f(i)=i*\sum_{j=1}^i\sigma(i*j)$与$g(i)=i*\sigma(i*i)$

首先挖掘一下$\sigma(x*y)$的计算方法，下面给出结论：

$$\sigma(x*y)=\sum_{u|x}\sum_{v|y}[\gcd(u,\frac{y}{v})=1]*u*v\\ =\sum_{u|x}\sum_{v|y}[\gcd(u,v)=1]*\frac{u*y}{v}$$
证明的话有特殊推广到一般：不妨$x=p^a,y=p^b$

需要统计的答案为$\sum_{i=0}^{a+b}p^i=\sum_{i=0}^bp^i+p^b\sum_{i=1}^{a}p^i$

也就是说如果$p\not| u$则$v$随意取值，如果$p|u$则$v=p^b$

质因数个数超过一个时可以同理转化

把上述计算方法套上莫比乌斯反演可得：

$$\sigma(x*y)=\sum_{u|x}\sum_{v|y}\sum_{d|x,d|y}\mu(d)*\frac{u*y}{v}\\ $$

$$f(x)=x\sum_{y=1}^{x}\sum_{u|x}\sum_{v|y}\frac{u*y}{v}\sum_{d|u,d|v}\mu(d)\\ =x\sum_{y=1}^{x}\sum_{d|x,d|y}\mu(d)\sum_{d|u,u|x}\sum_{d|v,v|y}\frac{uy}{v}\\ =x\sum_{y=1}^{x}\sum_{d|x,d|y}\mu(d)*d\sum_{u|\frac{x}{d}}\sum_{v|\frac{y}{d}}\frac{u*\frac{y}{d}}{v}\\ =x\sum_{y=1}^{x}\sum_{d|x,d|y}\mu(d)*d*\sigma(\frac{x}{d})\sigma(\frac{y}{d})\\ =x\sum_{d|x}\mu(d)*d*\sigma(x/d)*\sum_{y=1}^{x/d}\sigma(y)$$

$\sigma(x)$通过线筛，$\sum_{y=1}^{x/d}\sigma(y)$可以预处理前缀和，可以在$O(nlogn)$解决

$g(x)$类似处理即可

$$g(x)=x*\sum_{u|x}\sum_{v|y}\frac{u*x}{v}\sum_{d|u,d|v}\mu(d)\\ =x\sum_{d|x}\mu(d)\sum_{d|u,u|x}\sum_{d|v,v|x}\frac{ux}{v}\\ =x\sum_{d|x}\mu(d)*d\sum_{u|\frac{x}{d}}\sum_{v|\frac{x}{d}}\frac{u*\frac{x}{d}}{v}\\ =x\sum_{d|x}\mu(d)*d*\sigma(\frac{x}{d})\sigma(\frac{x}{d})\\ $$
预处理$f(x),g(x)$的前缀和，$O(nlogn)$预处理，$O(1)$查询