$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i,j]$$ $$=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\dfrac{ij}{(i,j)} $$$$=\sum\limits_{d=1}^n\dfrac{\sum\limits_{i=1}^{[\frac{n}{d}]}\sum\limits_{j=1}^{[\frac{n}{d}]}[(i,j)=1]idjd}{d} $$$$=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{[\frac{n}{d}]}\sum\limits_{j=1}^{[\frac{n}{d}]}[(i,j)=1]ij $$$$=-\sum\limits_{d=1}^nd+2\sum\limits_{d=1}^nd\sum\limits_{i=1}^{[\frac{n}{d}]}\sum\limits_{j=1}^{i}[(i,j)=1]ij $$

考虑 SP5971 的 Trick，把 $\sum\limits_{j=1}^i[(i,j)=1]j$ 变成 $\dfrac{\varphi(j)j}{2}$。

$$=\sum\limits_{d=1}^nd+2\sum\limits_{d=1}^nd\sum\limits_{i=1}^{[\frac{n}{d}]}\dfrac{\varphi(i)i^2}{2} $$$$=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{[\frac{n}{d}]}\varphi(i)i^2 $$

然后直接枚举 $d$，调和级数预处理即可。$O(n\log n+q)$