[BZOJ 3944]Sum

Description

求 $ans1=sumlimits_{i=1}^n varphi(i)$ 和 $ans2=sumlimits_{i=1}^n mu(i)$ 。 $n<2^{31}$ ，多组询问。

Input

一共T+1行

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

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

Output

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

Sample Input

6
1
2
8
13
30
2333

Sample Output

1 1
2 0
22 -2
58 -3
278 -3
1655470 2

题解

杜教筛的板子。已经有许多博客有讲，我也不凑这个热闹了。

记 $S_n$ 为积性函数的前缀。

对于 $mu$ ： $$S(n)=1-sum_{i=2}^nSleft(leftlfloorfrac{n}{i} ight floor ight)$$

对于 $varphi$ ： $$S(n)=frac{n(n+1)}{2}-sum_{i=2}^nSleft(leftlfloorfrac{n}{i} ight floor ight)$$

取 $2333333$ 作为阈值，线性筛出之前的，然后记忆化之后的。

 1 //It is made by Awson on 2018.1.24
 2 #include <set>
 3 #include <map>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <queue>
 7 #include <stack>
 8 #include <cstdio>
 9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Abs(a) ((a) < 0 ? (-(a)) : (a))
17 #define Max(a, b) ((a) > (b) ? (a) : (b))
18 #define Min(a, b) ((a) < (b) ? (a) : (b))
19 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
20 #define writeln(x) (write(x), putchar('
'))
21 #define lowbit(x) ((x)&(-(x)))
22 using namespace std;
23 const int N = 2333333;
24 void read(LL &x) {
25     char ch; bool flag = 0;
26     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
27     for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
28     x *= 1-2*flag;
29 }
30 void write(LL x) {
31     if (x > 9) write(x/10);
32     putchar(x%10+48);
33 }
34 
35 LL mu[N+5], phi[N+5], n;
36 struct num {
37     LL ans1, ans2;
38     num() {}
39     num(LL _ans1, LL _ans2) {ans1 = _ans1, ans2 = _ans2; }
40 }ans;
41 map<LL, num>mp;
42 
43 int prime[N+5], isprime[N+5], tot;
44 void get_pre() {
45     memset(isprime, 1, sizeof(isprime)); isprime[1] = 0, mu[1] = phi[1] = 1;
46     for (int i = 2; i <= N; i++) {
47     if (isprime[i]) prime[++tot] = i, mu[i] = -1, phi[i] = i-1;
48     for (int j = 1; j <= tot && i*prime[j] <= N; j++) {
49         isprime[i*prime[j]] = 0;
50         if (i%prime[j]) mu[i*prime[j]] = -mu[i], phi[i*prime[j]] = phi[i]*(prime[j]-1);
51         else {mu[i*prime[j]] = 0, phi[i*prime[j]] = phi[i]*prime[j]; break; }
52     }
53     mu[i] += mu[i-1], phi[i] += phi[i-1];
54     }
55 }
56 num Less (const num &a, const num &b) {num ans; ans.ans1 = a.ans1 - b.ans1, ans.ans2 = a.ans2-b.ans2; return ans; }
57 num Times (const num &a, const LL &x) {num ans; ans.ans1 = a.ans1*x , ans.ans2 = a.ans2*x; return ans; }
58 num cal(LL x) {
59     if (x <= N) return num(phi[x], mu[x]);
60     if (mp.count(x)) return mp[x];
61     num ans = num(x*(x+1)/2, 1);
62     for (LL i = 2, last; i <= x; i = last+1) {
63     last = x/(x/i); ans = Less(ans, Times(cal(x/i), (last-i+1)));
64     }
65     return mp[x] = ans;
66 }
67 void work() {
68     read(n); ans = cal(n);
69     write(ans.ans1), putchar(' ');
70     if (ans.ans2 < 0) putchar('-'), writeln(-ans.ans2);
71     else writeln(ans.ans2);
72 }
73 int main() {
74     get_pre(); LL t; read(t);
75     while (t--) work();
76     return 0;
77 }