[BZOJ 4805] 欧拉函数求和

题目大意

给定 nn,求

i=1nφ(i)\sum_{i = 1}^{n} \varphi(i)

1n2,000,000,0001 \leqslant n \leqslant 2,000,000,000

题目链接

BZOJ 4805

题解

杜教筛模版题。

狄利克雷卷积有 φ×1=id\varphi \times 1 = id,则有:

Φ(n)=n(n+1)2i=2nΦ(ni)\Phi(n) = \frac{n (n + 1)}{2} - \sum_{i = 2}^{n} \Phi(\lfloor \frac{n}{i} \rfloor)

预处理出前 n23n^{\frac{2}{3}} 项,复杂度为 O(n23)O(n^{\frac{2}{3}})

代码

< MAXNN 写成了 <= MAXNN,RE了四次。。。

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
#include <cstdio>
#include <map>
const int MAXNN = 1600000;
long long phi[MAXNN];
int prime[MAXNN], primeCnt;
bool notPrime[MAXNN];
void linearShaker() {
phi[1] = 1;
notPrime[0] = notPrime[1] = true;
for (int i = 2; i < MAXNN; i++) {
if (!notPrime[i]) {
prime[++primeCnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= primeCnt && i * prime[j] < MAXNN; j++) {
notPrime[i * prime[j]] = true;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for (int i = 2; i < MAXNN; i++) phi[i] += phi[i - 1];
}
long long pSumPhi(int n) {
if (n < MAXNN) return ::phi[n];
static std::map<int, long long> phi;
std::map<int, long long>::iterator it;
if ((it = phi.find(n)) != phi.end()) return it->second;
long long res = (long long) n * (n + 1) / 2;
int last;
for (int i = 2; i <= n; i = last + 1) {
last = n / (n / i);
res -= (last - i + 1) * pSumPhi(n / i);
}
return phi[n] = res;
}
int main() {
int n;
scanf("%d", &n);
linearShaker();
printf("%lld\n", pSumPhi(n));
return 0;
}