[tex]Calculate \sum_{1\le i<j\le n}{\gcd(i,j)}.\\ \begin{align*}&\sum_{1\le i<j\le n}{\gcd(i,j)}\\=&\sum_{1\le i<n}{\sum_{i<j\le n}{\gcd(i,j)}}\\=&\sum_{1<i\le n}{\sum_{1\le j<i}{\gcd(i,j)}}\\=&\sum_{1\le i\le n}{\sum_{d\mid i}{d\varphi(\frac{i}{d})}}.\end{align*}\\O(n\sqrt{n})~or~O(n\log{n}).\\ \begin{align*}=&\sum_{1\le d\le n}{\sum_{1\le i\le \frac{n}{d}}{\varphi(i)}}\\=&\sum_{1\le d\le n}{Sum\varphi_{\frac{n}{d}}}.\end{align*}\\O(n).\\ \begin{align*}d\rightarrow \frac{n}{\frac{n}{d}}.\end{align*}\\O(\sqrt{n}).\\ \begin{align*}for(x,y)=1,\\&(\sum_{x\mid n}{x\varphi(\frac{n}{x})})(\sum_{y\mid n}{y\varphi(\frac{n}{y})})\\=&\sum_{xy\mid n}{xy\varphi(\frac{n}{xy})}.\end{align*}\\O(1).[/tex]

注意……以上默认[tex]\varphi(1)=0[/tex]……然后就是上面的所有时间复杂度……均指询问复杂度……预处理的话可以线性，参考欧拉筛法。