先去常规拆式子：
\[\sum_{i=1}^n\sum_{j=1}^n (i,j)^{i+j}
\]
\[=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n[(i,j)=d]d^{i+j}
\]
\[=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[(i,j)=1]d^{d(i+j)}
\]
\[=\sum_{d=1}^n\sum_{c=1}^{\lfloor\frac{n}{d}\rfloor}\mu(c)\sum_{i=1}^{\lfloor\frac{n}{cd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{cd}\rfloor}d^{cd(i+j)}
\]
\[=\sum_{d=1}^n\sum_{c=1}^{\lfloor\frac{n}{d}\rfloor}\mu(c)(\sum_{i=1}^{\lfloor\frac{n}{cd}\rfloor}d^{cdi})(\sum_{j=1}^{\lfloor\frac{n}{cd}\rfloor}d^{cdj})
\]
\[=\sum_{d=1}^n\sum_{c=1}^{\lfloor\frac{n}{d}\rfloor}\mu(c)(\sum_{i=1}^{\lfloor\frac{n}{cd}\rfloor}d^{cdi})^2
\]
那么设 \(f(d,p)=\sum_{i=1}^p d^i\)，则 \(\sum_{i=1}^{\lfloor\frac{n}{cd}\rfloor}d^{cdi}=f(d^cd,\lfloor\frac{n}{cd}\rfloor)\)。那么对于这个等比数列求和，我们发现如果直接求通项公式需要求逆元，那么还不如直接类似分治处理呢：
\[f(d,p)=\begin{cases}(d^\frac{n}{2}+1)f(d,\frac{n}{2})&n\equiv 0\pmod 2\\d^n+f(d,n-1)&n\equiv 1 \pmod 2\end{cases}
\]
但是会发现这个东西实际上是 \(O(n\log n)\) 级别的，所以直接枚举做就行了。
