瞎jb推一波式子，推出
\[ans=n^{x+y}\sum_{j=0}^{y+1}a_j\sum_{i|n}\sum_{d_1|n/i}i^{j-x}d_1^{y-x}\mu(d_1)
\]
其中 \(a_j\) 是自然数幂和的多项式系数。
然后后面显然是个积性函数，随便求求就好了。
\[\begin{aligned}
\frac{ans}{n^y}&=\sum_{d\mid n}d^{x-y}\sum_{i=1}^{n}[gcd(i,n)=d]i^y\\
&=\sum_{d\mid n}d^{x-y}\sum_{j=1}^{n/d}[\gcd(j,n/d)=1](jd)^y\\
&=\sum_{d\mid n}d^{x}\sum_{j=1}^{n/d}[\gcd(j,n/d)=1]j^y\\
&=\sum_{d\mid n}d^{x}f(n/d)\\
\end{aligned}
\]
\[\begin{aligned}
f(n)&=\sum_{i=1}^{n}[\gcd(i,n)=1]i^y\\
&=\sum_{d|n}\mu(d)d^y\sum_{i=1}^{n/d}i^y
\end{aligned}
\]
\[\begin{aligned}
ans&=n^y\sum_{d_1\mid n}d_1^{x}\sum_{d_2\mid n/d_1}\mu(d_2)d_2^y\sum_{i=1}^{n/d_1/d_2}i^y\\
\end{aligned}
\]
\[\frac{ans}{n^y}=\sum_{i|n}^{n}g(i,y)\sum_{d1\times d2=n/i}d_1^x\mu(d_2)d_2^y=\sum_{i|n}\sum_{j=0}^{y}a_ji^j\sum_{d_1|n/i}^{n/i}(n/i/d_1)^x\mu(d_1)d_1^y=\sum_{j=0}^{y}a_j\sum_{i|n}i^j\sum_{d_1|n/i}\frac{n^x}{(id_1)^x}\mu(d_1)d_1^y
\]
\[g(n,k)=\sum_{i|n}\sum_{j|n/i}i^{k-x}j^{y-x}\mu(j)\\
g(p^c, k)=\sum_{i|p^c}\sum_{j|p^c/i}j^{k-x}\mu(i)i^{y-x}=\sum_{i|p^c}i^{k-x}-p^{y-x}\sum_{i|p^{c-1}}i^{k-i}
\]