最近被51NOD的数论题各种刷……（NOI快到了我在干什么啊！
然后发现这题在网上找不到题解……那么既然A了就来骗一波访问量吧……
（然而并不怎么会用什么公式编辑器，写得丑也凑合着看吧……
$$
ANS=\sum_{i=1}^{n}\sum_{j=1}^{n} \frac{i*j}{gcd(i,j)}
$$
$$
=\sum_{d=1}^{n} d*\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor} i*j*[gcd(i,j)==1]
$$
$$
=\sum_{d=1}^{n} d*\sum_{d'=1}^{\left\lfloor\frac{n}{d}\right\rfloor} f(\left\lfloor\frac{n}{d*d'}\right\rfloor)*d'^2*μ(d')
$$
$$
=\sum_{d'=1}^{n} d'^2*μ(d')*\sum_{d=1}^{\left\lfloor\frac{n}{d'}\right\rfloor} d*f(\left\lfloor\frac{n}{d*d'}\right\rfloor)
$$
这里$f(x)=(\frac{x*(x+1)}{2})^2$，即1到x中数字之间两两乘积之和。
可以看出不同的$\left\lfloor\frac{n}{d'}\right\rfloor$只有根号n个，对于某一个$\left\lfloor\frac{n}{d'}\right\rfloor$，不同的$\left\lfloor\frac{n}{d*d'}\right\rfloor$也只有根号n个，那么把它们压在一起处理就好了。
但是要做到这一点需要快速求出$d'^2*μ(d')$的前缀和，这时就要用上杜教筛了。
记$g(x)=x^2*μ(x)$，$S(x)=\sum_{i=1}^{x} g(i)$
那么
$ \sum_{i=1}^{n} \sum_{x|i} g(x)*(\frac{i}{x})^2$
$=\sum_{i=1}^{n} i*\sum_{x|i} μ(x)$
$=\sum_{i=1}^{n} [i==1] $
$= 1$
同时
$ \sum_{i=1}^{n} \sum_{x|i} g(x)*(\frac{i}{x})^2$
$=\sum_{i=1}^{n} \sum_{x=1}^{[\frac{n}{i}]} g(x)*i^2$
$=\sum_{i=1}^{n} i^2*S[\frac{n}{i}]$
可以得到$S(n)=1-\sum_{i=2}^{n} i^2*S[\frac{n}{i}]$，预处理+哈希维护一波就行了
但是不知道是我常数太大，还是方法没别人优越，卡了很久常数才卡过去。
代码自己码啦！