先要推式子
\[
\begin{aligned}
\varphi(x)\varphi(y)&=(x\prod_{p|x}\frac{p-1}p)(y\prod_{p|y}\frac{p-1}p)\&=(\prod_{p|xy}\frac{p-1}p)(\prod_{p|\gcd(x,y)}\frac{p-1}p)xy\&=\varphi(xy)\varphi(\gcd(x,y))xy
\end{aligned}
\\\Rightarrow
\varphi(xy)=\frac{\varphi(x)\varphi(y)\gcd(x,y)}{\varphi(\gcd(x,y))}\\]
接着堆式子
\[
\begin{aligned}
ans&=\sum_i\sum_{i}\varphi(a_ia_j)dis(i,j)\&=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_i\sum_j\varphi(a_i)\varphi(a_j)dis(i,j)[\gcd(a_i,a_j)=d]
\f(d)&=\sum_i\sum_j...[\gcd(a_i,a_j)=d]
\g(d)&=\sum_{d|x}f(x)\&=\sum_i\sum_j...[d|\gcd(a_i,a_j)]\&=\sum_{d|a_i}\sum_{d|a_j}\varphi(a_i)\varphi(a_j)(dep_i+dep_j-2dep_{lca(i,j)})\&=\sum_{d|a_i}\varphi(a_i)\sum_{d|a_j}\varphi(a_j)(dep_i+dep_j-2dep_{lca(i,j)})\&=2\sum_{d|a_i}\varphi(a_i)dep_i\sum_{d|a_j}\varphi(a_j)-2\sum_{d|a_i}\varphi(a_i)\sum_{d|a_j}\varphi(a_j)*dep_{lca(i,j)}
\f(d)&=\sum_{d|x}\mu(\frac{x}d)g(x)=\sum_{i=1}^{\lfloor\frac{n}d\rfloor}\mu(i)g(di)
\ans&=\sum_{d=1}^n\frac{d}{\varphi(d)}f(d)\&=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}d\rfloor}\mu(i)g(di)\&=\sum_{T=1}^ng(T)\sum_{d|T}\mu(\frac{T}d)\frac{d}{\varphi(d)}
\h(T)&=\sum_{d|T}\mu(\frac{T}d)\frac{d}{\varphi(d)}
\\end{aligned}
\]
留意到\(h(T)\)可以直接筛。而\(g(T)\)也是可以“筛”的（建立虚树，自底向上的带权根径覆盖）,然后把这俩玩意儿数乘……
简直绝了，复杂度是\(O(b\log n)\)级别的
代码留坑……
原文：https://www.cnblogs.com/nosta/p/11033914.html