比起加强版，原题面的式子要更绕一些，毕竟这个直接给了你 (mu)。
我们一如往常的推式子。
[largesum_{i=1}^nsum_{j=1}^n(i+j)^k ext{gcd}(i,j)mu^2( ext{gcd}(i,j))
]
先处理一下 ( ext{gcd})。
[largesum_{d=1}^nsum_{i=1}^nsum_{j=1}^n[ ext{gcd}(i,j)=d](i+j)^kdmu^2(d)
]
顺便还能把 (d) 提出来。
[large{
egin{aligned}
&sum_{d=1}^ndmu^2(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}(id+jd)^k[ ext{gcd}(i,j)=1]\
&sum_{d=1}^nd^{k+1}mu^2(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}(i+j)^k[ ext{gcd}(i,j)=1]
end{aligned}
}
]
式子太长，中间那一坨很明显可以简写一下，可以方便之后代码的处理。
[large F(n)=sum_{i=1}^nsum_{j=1}^n(i+j)^k
]
我们继续推，接下来按套路来就好。
[large{
egin{aligned}
&sum_{d=1}^nd^{k+1}mu^2(d)F(lfloorfrac{n}{d}
floor)[ ext{gcd}(i,j)=1]\
&sum_{d=1}^nd^{k+1}mu^2(d)F(lfloorfrac{n}{d}
floor)sum_{pmid i,pmid j}mu(p)
end{aligned}
}
]
从枚举 (d) 中得到启发，枚举 (p)（这是废话）。在枚举时，原来的 (i) 和 (j) 一样会被提出个 (p^k)。
[large sum_{d=1}^nd^{k+1}mu^2(d)sum_{p=1}^{lfloorfrac{n}{d}
floor}mu(p)p^kF(frac{n}{dp})
]
套路地设 (T=dp)。
[large {
egin{aligned}
&sum_{T=1}^nsum_{dmid T}d^{k+1}mu^2(d)mu(frac{T}{d})(frac{T}{d})^kF(frac{n}{T})\
&sum_{T=1}^nsum_{dmid T}dmu^2(d)mu(frac{T}{d})(frac{T}{d})^kd^kF(frac{n}{T})\
&sum_{T=1}^nT^kF(frac{n}{T})sum_{dmid T}dmu^2(d)mu(frac{T}{d})
end{aligned}
}
]
后面一坨全是积性函数的狄利克雷卷积式的组合,撮合到一起也是个积性函数，那么我们设 ：
[large G(n)=sum_{dmid n}dmu^2(d)mu(frac{n}{d})
]
就有：
[largesum_{T=1}^nT^kF(frac{n}{T})G(T)
]
接下来的难点就在于处理那两个函数了。
我们设 (t[i]) 为一个数 (i) 在函数 (F) 中产生贡献的次数，则有：
[large F(n)=sum_{i=1}^nsum_{j=1}^n(i+j)^k=sum_{i=2}^{2n}t[i]i^k
]
不难发现，(t[i]) 的值是有规律的，你可以画个表格模拟这两个 (sum)。
发现 (t[i]= ext{min}(i-1,2n-i+1))。
如果设 (V(n)=sum_{i=1}^n(n-i+1)i^k)，
那么 (F(n)=V(2n)-2V(n))。
递推处理即可。
对于函数 (G)，已知它是积性函数，那我们先考虑 (G(p^c)) 的简单情况，其中 (p) 是一个素数。
我们结合莫比乌斯函数的定义式并稍加运算，得出：
(c=1)，(G(p)=p-1)。
(c=2)，(mu) 函数出现了 (0)，故产生贡献时， (dmid p)，此时 (G(p^2)=-p)。
(c=3)，(mu(d)) 和 (mu(frac{T}{d})) 同时存在，一定有一个值为 (0)，所以此时 (G(p^c)=0)。
(c=0) 不用说。。。
( ext{CODE})
#include <bits/stdc++.h>
#define N 20000010
#define ll unsigned int
// 内存给得太小，小心点用~ 模数自然溢出就行
using namespace std;
template <typename T>
inline void read (T &a) {
T x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
(ch == '-') and (f = 0);
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + (ch ^ '0');
ch = getchar ();
}
a = f ? x : -x;
}
template <typename T, typename ...A>
inline void read (T &t, A &...a) {
read (t), read (a...);
}
template <typename T>
inline void print (T x) {
if (x < 0) putchar ('-'), x = -x;
if (x > 9) print (x / 10);
putchar (x % 10 + '0');
}
inline ll qpow (ll a, ll b) {
ll ret = 1;
while (b) {
(b & 1) and (ret = ret * a);
a = a * a;
b >>= 1;
}
return ret;
}
int pri[N], cnt, k;
ll ans, f[N], g[N]; // 对应上文函数
bool is[N];
inline void phigros (int n) { //线筛
f[1] = g[1] = 1;
for (int i = 2; i <= n; i++) {
(! is[i]) and (g[i] = i - 1, f[i] = qpow (i, k), pri[++cnt] = i);
// g[i] 正常赋值，猜猜这里的 f 是啥QWQ。
for (int j = 1; j <= cnt and i * pri[j] <= n; j++) {
is[i * pri[j]] = 1;
f[i * pri[j]] = f[i] * f[pri[j]];
if (i % pri[j] == 0) { // 这里是之前 g 的部分情况
int res = i / pri[j];
if (res % pri[j]) g[i * pri[j]] = g[res] * (-pri[j]);
break;
}
g[i * pri[j]] = g[i] * g[pri[j]];
}
}
for (int i = 2; i <= n; i++) {
g[i] = g[i - 1] + g[i] * f[i];
f[i] += f[i - 1];
}
for (int i = 2; i <= n; i++) {
f[i] += f[i - 1];
} // 如前文所述
}
int t, n;
signed main () {
read (t, n, k);
phigros (n << 1);
while (t--) {
read (n);
ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans += (g[r] - g[l - 1]) * (f[(n / l) << 1] - (f[n / l] << 1));
}
print (ans);
printf ("
");
}
}