题意：给出 ，对于 ，分别求 ，，时限 。
记 为 的答案。令 ，，用 来拆解 。
记 。线性筛出
后，对 进行差分，可以发现是 的部分和。
预处理 之后
已经可以整除分块，但我们不满足于这个形式，进行差分
记 ，则 。 是积性函数，用“快速卷积性函数”可做到
。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <algorithm>
#include <cstdio>
using uint = unsigned int;
const int MaxN = 10050000;
uint powM(uint a, int t) {
uint ret = 1;
while (t) {
if (t & 1)
ret *= a;
a *= a;
t >>= 1;
}
return ret;
}
uint S[MaxN*2], f[MaxN];
int p[MaxN/7], totP;
bool flag[MaxN*2];
void sieve(int n, int k) {
S[1] = f[1] = flag[1] = 1;
for (int i=1; i<=2*n; i++) {
if (!flag[i]) {
p[++totP] = i;
S[i] = powM(i, k);
if (i<=n)
f[i] = 1;
}
for (int j = 1; j<=totP; j++) {
int t = p[j] * i;
if (t>2*n) break;
flag[t] = true;
S[t] = S[i] * S[p[j]];
if (i%p[j]==0) break;
if (t<=n)
f[t] = f[i];
}
}
p[++totP] = 2*n+1;
for (int i=1; i<=2*n; i++)
S[i] += S[i-1];
for (uint i = 1; i<=n; i++) {
if (f[i])
f[i] = i;
S[i] = S[2*i] + S[2*i-1] - 2*S[i];
}
for (int i = 1; p[i] <= n; i++) {
static uint sav[MaxN];
std::copy(S+1, S+n/p[i]+1, sav+1);
for (long long d=p[i]; d<=n; d*=p[i]) {
uint buf = (f[d] - f[d/p[i]]) * powM(d, k);
for (int t=1; t*d<= n; t++)
S[t*d] += sav[t]*buf;
}
}
for (int i=1; i<=n; i++)
S[i] += S[i-1];
}
int main() {
int T, N, K;
scanf("%d%d%d", &T, &N, &K);
sieve(N, K);
while (T--) {
scanf("%d", &N);
printf("%u\n", S[N]);
}
return 0;
}
|