[BZOJ 3944] Sum

发表于2017-05-03更新于2020-08-06

题目大意

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

1⩽T⩽101 \leqslant T \leqslant 10

0⩽n<2310 \leqslant n < 2^{31} （为什么会有 00。。。）

题目链接

BZOJ 3944

题解

杜教筛模版题。

狄利克雷卷积有 φ×1=id\varphi \times 1 = id 、mu×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;
}