$$
\begin {aligned}
ANS & = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n (i + j) ^ K (i, j)\mu ^ 2((i, j)) \\
& = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n (i + j) ^ K \sum _ {d = 1} ^ n d\mu ^ 2(d) [gcd(i, j) = d]\\
& = \sum _ {d = 1} ^ n d\mu ^ 2(d) \sum _ {i = 1} ^ {\lfloor \frac n d\rfloor } \sum _ {j = 1} ^ {\lfloor \frac n d\rfloor } (id + jd) ^ K [gcd(i, j) = 1]\\
& = \sum _ {d = 1} ^ n d ^ {K + 1}\mu ^ 2(d) \sum _ {i = 1} ^ {\lfloor \frac n d\rfloor } \sum _ {j = 1} ^ {\lfloor \frac n d\rfloor } (i+ j) ^ K \sum _ {e | (i, j)} \mu(e)\\
& = \sum _ {d = 1} ^ n d ^ {K + 1}\mu ^ 2(d) \sum _ {e = 1} ^ n \mu(e)\sum _ {i = 1} ^ {\lfloor \frac n {de}\rfloor } \sum _ {j = 1} ^ {\lfloor \frac n {de}\rfloor } (ie+ je) ^ K \\
& = \sum _ {d = 1} ^ n d ^ {K + 1}\mu ^ 2(d) \sum _ {e = 1} ^ n \mu(e)e ^ K\sum _ {i = 1} ^ {\lfloor \frac n {de}\rfloor } \sum _ {j = 1} ^ {\lfloor \frac n {de}\rfloor } (i + j) ^ K \\
& = \sum _ {T = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n T\rfloor } \sum _ {j = 1} ^ {\lfloor \frac n T\rfloor } (i + j) ^ K \sum _ {d | T} d ^ {K + 1} \mu ^ 2(d) \mu(\frac T d) (\frac T d) ^ K \\
& = \sum _ {T = 1} ^ n T^ K \sum _ {i = 1} ^ {\lfloor \frac n T\rfloor } \sum _ {j = 1} ^ {\lfloor \frac n T\rfloor } (i + j) ^ K \sum _ {d | T} d \mu ^ 2(d) \mu(\frac T d) \\
\end {aligned}
$$
现在考察 $S(n) = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n (i + j) ^ K$ 的计算。记 $f(n) = \sum _ {i = 1} ^ n i ^ K, g(n) = \sum _ {i = 1} ^ n f(i)$ 。
$$
\begin {aligned}
S(n) - S(n - 1) & = \sum _ {j = 1} ^ n (n + j) ^ K + \sum _ {i = 1} ^ {n - 1} (i + n) ^ K \\
& = f(2n) - f(n) + f(2n - 1) - f(n) \\
& = f(2n) + f(2n - 1) - 2f(n)
\end {aligned}
$$
$$
\begin {cases}
S(n) - S(n - 1) = f(2n) + f(2n - 1) -2f(n) \\
S(n - 1) - S(n - 2) = f(2n - 2) + f(2n - 3) -2f(n - 1) \\
\dots \\
S(1) - S(0) = f(2) + f(1) - 2f(1)
\end {cases}
$$
将式子加起来，将每个式子的前两项加起来，后一项加起来，那么有 $S(n) = g(2n) - 2g(n)$ 。
现在考察 $f(n) = \sum _ {d | T} d \mu ^ 2(d) \mu(\frac T d)$ 的计算，显然是个积性函数，只需考察 $n = p ^ k$ 的 $f(n)$ 。
$$
f(p ^ k) = \begin {cases}
\mu ^ 2(1) \mu(1) = 1, k = 0 \\
\mu ^ 2(1) \mu(p) + p \mu ^ 2 (p) \mu (1) = -1 + p, k = 1 \\
\mu ^ 2 (1) \mu (p ^ 2) + p \mu ^ 2(p) \mu (p) + p ^ 2 \mu^2(p ^ 2) \mu(p) = -p, k = 2 \\
0, k \ge 3
\end {cases}
$$
对于 $k \ge 3$ ，$\mu(d)$ 和 $\mu(\frac T d)$ 中至少有一项含有 $2$ 及以上次幂，为 $0$ 。
对于这个式子，可以数论分块，复杂度 $O(n + \frac {n \log K} {\ln n} + q\sqrt n)$ 。
查看代码
1 |
|