钦定 \(i>j\)，研究得 \((x^i-1,x^j-1)\rightleftharpoons(x^i-x^j,x^j-1)\rightleftharpoons(x^j(x^{i-j}-1),x^j-1)\)，注意到 \((x^j,x^j-1)=1\) 且当 \((a,c)=1\) 时 \((ab,c)=(a,b)(a,c)\)，则原式 \(\rightleftharpoons(x^{i-j}-1,x^j-1)\rightleftharpoons(x^{i\bmod j}-1,x^j-1)\rightleftharpoons x^{(i,j)}-1\)。
于是题目即求 \(\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^nx^{(i,j)}\right)-n^2\)。注意到 \(1\leqslant(i,j)\leqslant n\)，容易想到研究每一个 \((i,j)\) 的贡献次数，设其为 \(f(x)\)，显然有 \(f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=x]\)，观察得 \(f(x)=2\times\left(\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}\varphi(i)\right)-1\)，则答案为 \(\sum\limits_{i=1}^nx^i\cdot f(i)\)，整除分块 & 等比数列求和优化即可。
原文：https://www.cnblogs.com/orchid-any/p/15182527.html