[BZOJ 3944] Sum

题目大意

给定 nn ,求 i=1nφ(i)\sum_{i = 1}^{n} \varphi(i)i=1nμ(i)\sum_{i = 1}^{n} \mu(i),多组询问。

1T101 \leqslant T \leqslant 10

0n<2310 \leqslant n < 2^{31} (为什么会有 00。。。)

题目链接

BZOJ 3944

题解

杜教筛模版题。

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

\begin{align} \Phi(n) &= \frac{n (n + 1)}{2} - \sum_{i = 2}^{n} \Phi(\lfloor \frac{n}{i} \rfloor) \\ M(n) &= 1 - \sum_{i = 2}^{n} M(\lfloor \frac{n}{i} \rfloor) \end{align}

这道题 RE、WA、TEL 了一共大概 2020 次,其中四五次是和 BZOJ 4805 一样的原因,一些是重写了一遍少些了一句的 TLE,一些是蜜汁 RE,一些是蜜汁运算中过了 int (好像)而 WA 。。。因为太惨不忍睹了,所以以上有一半是开了小号交的。。。

代码

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