BZOJ 3944: sum

Description

给你一个正整数N,N<2^31, 求$\sum_{i=1}^n \phi (i)$和$\sum_{i=1}^n \mu (i)$

Input

一共T+1行

第1行为数据组数T(T<=10)

第2~T+1行每行一个正整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

Sample Output

Solution

令F(n)为f(n)的前缀和，G(n)为g(n)的前缀和，且满足$g(n)=\sum_{i|n}f(i)$，则有：

\begin{align}

G(n)&=\sum_{i=1}^ng(i) \

&=\sum_{j=1}^n\sum_{j|i}f(j)\

&=\sum_{j=1}^n\lfloor\frac n j \rfloor f(j) \

&=\sum_{j=1}^nF(\lfloor\frac n j \rfloor) \

\end{align}

$$ \therefore F(n)=G(n)-\sum_{i=2}^nF(\lfloor\frac n i \rfloor) $$

若G(n)可以在O(1)时间内算出，则F(n)可以在O(n^(3/4))的时间内算出(别问我复杂度是咋算的)

如果预处理前O(n^(2/3)) 的部分，则F(n)可以在O(n^(2/3))的时间内算出

然后疯狂TLE。。。抄了POPOQQQ的实现。

Code

 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
72
73
74
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int INF = 1000000007;
const int maxn = 5000010;
map<int, LL> M, S;
map<int, LL>::iterator it;
int cnt;
bool vis[maxn];
LL p[350003], phi[maxn], mu[maxn];

LL F(int n) {
    if (n <= 5000000) return phi[n];
    if ((it = M.find(n)) != M.end()) return it->second;
    LL ret = LL(n)*LL(n+1ll)/2ll;
    for (LL i = 2ll, k; i <= n; i = k + 1ll) {
        k = n / (n / i);
        ret -= (k-i+1ll) * F(n/i);
    }
    return M[n] = ret;
}

LL G(int n) {
    if (n <= 5000000) return mu[n];
    if ((it = S.find(n)) != S.end()) return it->second;
    LL ret = 1ll;
    for (LL i = 2ll, k; i <= n; i = k + 1ll) {
        k = n / (n / i);
        ret -= (k-i+1ll) * G(n/i);
    }
    return S[n] = ret;
}

inline void precal() {
    phi[1] = mu[1] = 1ll;
    for (LL i = 2; i <= 5000000; ++i) {
        if (!vis[i]) {p[cnt++] = i;phi[i] = i-1ll;mu[i] = -1ll;}
        for (int j = 0; j < cnt && i*p[j] <= 5000000ll; ++j) {
            vis[i*p[j]] = true;
            if (i%p[j] == 0ll) {
                phi[i*p[j]] = p[j] * phi[i];
                mu[i*p[j]] = 0ll;
                break;
            } else {
                phi[i*p[j]] = (p[j]-1ll)*phi[i];
                mu[i*p[j]] = -1ll*mu[i];
            }
        }
    }
    for (int i = 1; i <= 5000000; ++i) {
        phi[i] += phi[i-1];
        mu[i] += mu[i-1];
    }
}

int main() {
    int n, T;
    precal();
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%lld %lld\n", F(n), G(n));
    }
}