数个月前说要写，鸽到现在，菜。

属于是惊世骇俗的神秘题了。

拿到式子直接开始乱推:

$$ \sum_{i=1}^{n}{\gcd(i,n)^x \mathrm{lcm}(i,n)^y}\\ $$

$$   =\sum_{i=1}^{n}{i^yn^y\gcd(i,n)^{x-y}}\\ $$

$$   =n^y\sum_{d|n}{d^{x-y}\sum_{i=1}^{n}{i^y[\gcd(i,n)=d]}}\\ $$

$$   =n^y\sum_{d|n}{d^{x-y}\sum_{i=1}^{\frac{n}{d}}{(id)^y[\gcd(i,\frac{n}{d})=1]}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{i=1}^{\frac{n}{d}}{i^y\sum_{k|i,k|\frac{n}{d}}{\mu(k)}}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)\sum_{i=1}^{\frac{n}{dk}}{(ik)^y}}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y\sum_{i=1}^{\frac{n}{dk}}{i^y}}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^yS(\frac{n}{dk},y)}}\\ $$

玩原神的人都知道 $S(\frac{n}{dk},y)$ 是个 $y+1$ 次多项式，这就是原神带给我骄傲的资本。记 $S=\sum_{i=0}^{y+1}{f_ix^i}$ 代入：

$$ =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y\sum_{i=0}^{y+1}{f_i(\frac{n}{dk})^i}}}\\$$

$$  =n^y\sum_{i=0}^{y+1}{f_i\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y{(\frac{n}{dk})^i}}}}\\$$

$$  =n^y\sum_{i=0}^{y+1}{f_i(\mu \cdot Id^y \ast Id^x \ast Id^i)_{(n)}}\\$$

三个函数卷积，纯纯的卷狗。

好在三个积性函数卷出来也是积性函数，于是 pollard_rho 出 $n$ 的所有质因子分开算。

$$(\mu \cdot Id^y \ast Id^x \ast Id^i)_{(p^c)}\\$$

$$  =\sum_{j=0}^{c}{\mu(p^j)p^{yj}\sum_{k=0}^{c-j}{p^{kx}p^{(c-j-k)i}}}\\$$

$$  =\sum_{k=0}^{c}{p^{ci+(x-i)k}}-p^y\sum_{k=0}^{c-1}{p^{(c-1)i+(x-i)k}}\\$$

两坨都是等比数列求和，好好好，玩原神玩的。

最后就是这个 $f_i$。

如果你玩原神，那么你就会伯努利数，那么就知道：

$$\sum_{i=1}^{n}{i^k}=\frac{1}{k+1}\sum_{j=0}^{k}{(-1)^jC_{k+1}^jB_jn^{k+1-j}}$$

其中 $B_j$ 是伯努利数，可以用 EGF 求：

$$B(x)=\sum_{i \ge 0}{B_i\frac{x^i}{i!}}=\frac{x}{e^x-1}$$

然后就结束了。原神，启动！

听说还很卡常，已加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。