主要思路

先考虑莫比乌斯反演？

\[ \begin{aligned} ans &= \sum_{i = 1}^n \sum_{j = 1}^n f(\gcd(i, j))^k \\ &= \sum_{d = 1}^n f(d)^k \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d] \end{aligned} \]

经典化简：

\[ \begin{aligned} ans &= \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor^2 \sum_{x|T} \mu(x) f(\frac{T}{x})^k \end{aligned} \]

我们可以对这个 \(\lfloor \frac{n}{T} \rfloor^2\) 进行整除分块，所以问题的重心转移到了求后面那个 Dirichlet 卷积的前缀和身上。