JZPKIL

Link

Solution

$\begin{aligned} &\sum_{i=1}^n(i,n)^x[i,n]^y\\ =&n^y\sum_{i=1}^n(i,n)^{x-y}i^y\\ \end{aligned}$

依旧设

$f(x)=\sum_{d|x}g(d)$$g(x)=\sum_{d|x}\mu(\frac xd)f(d)$

那么

设

$S(n,x)=\sum_{i=1}^ni^x$

则

MDZZ。。。。被套路带偏。。重来。

$\begin{aligned} &\sum_{i=1}^n(i,n)^x[i,n]^y\\ =&n^y\sum_{i=1}^n(i,n)^{x-y}i^y\\ \end{aligned}$

怎样跑得更快，是可以引入辅助函数来把gcd去掉的，因为函数值可以暴力算。然而这个显然不行。。。

这样的话，前后部分独立，那就看后面的那个部分。设原式子为

$\begin{aligned} S(n)&=\sum_{i\perp n,i\le n}i^y\\ &=\sum_{i=1}^{n}i^y\sum_{d|i,d|n}\mu(d)\\ &=\sum_{d|n}\mu(d)\sum_{d|i}i^y\\ &=\sum_{d|n}\mu(d)d^y\sum_{i'=1}^{\frac nd}i^y \end{aligned}$

设

$S_k(n)=\sum_{i=1}^n i^k$$\begin{aligned} &\sum_{d|n}\mu(d)d^y\sum_{i'=1}^{\frac nd}i^y\\ =&\sum_{d|n}\mu(d)d^yS_y(\frac nd) \end{aligned}$

回代，

Code