题目描述

给定正整数$n$,求
$$
\begin{cases}
\Phi(n)=\sum\limits_{i=1}^{n} \phi(i) \\
M(n)=\sum\limits_{i=1}^{n} \mu(i)
\end{cases}
$$
其中$n \le 2^{32}-1$

题解

当然分别计算$\Phi(n)$和$M(n)$了

$\Phi(n)$

首先有$\phi \times 1=id$

其次还有$f \times g = h \Rightarrow g(1)F(n)=H(n)-\sum\limits_{d=2}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor)$

也就是说$\Phi(n)=ID(n)-\sum\limits_{d=2}^{n}1(d)\Phi(\lfloor \frac{n}{d} \rfloor)$

即$\Phi(n)=\frac{(1+n)n}{2}-\sum\limits_{d=2}^{n}\Phi(\lfloor \frac{n}{d} \rfloor)$

线性筛$\phi(n)$

线性筛处理前$n^{\frac{2}{3}}$后,单次可以做到$O(n^{\frac{2}{3}})$

假设当前枚举到了$i$和素数$p_j$

若$i$是素数,则$\phi(i)=i-1$

若$p_j \mid i$,设$i \times p_j=i’ \times p_j^k$,且$(i’,p_j^k)=1$,则$\phi(i \times p_j)=\phi(i’) \times \phi(p_j^k)$

同时,有$\phi(n)=n\Pi (\frac{p_i-1}{p_i})$成立

即$\phi(i \times p_j)=\phi(i’) \times p_j^k\frac{p_j-1}{p_j}=i’\Pi p_t^{k_t} \times p_j^{k-1}\frac{p_j-1}{p_j} \times p_j=\phi(i)p_j$

若$p_j \not \mid i \Rightarrow(i,p_j)=1$,则$\phi(i \times p_j)=\phi(i) \times \phi(p_j)=\phi(i) \times (p_j-1)$

$M(n)$

首先有$\mu \times 1 = \epsilon$

其次还有$f \times g = h \Rightarrow g(1)F(n)=H(n)-\sum\limits_{d=2}^{n}g(d)F(\lfloor \frac{n}{d} \rfloor)$

也就是说$M(n)=E(n)-\sum\limits_{d=2}^{n}1(d)M(\lfloor \frac{n}{d} \rfloor)$

即$M(n)=[n \ge 1]-\sum\limits_{d=2}^{n}M(\lfloor \frac{n}{d} \rfloor)$

线性筛$\mu(n)$

线性筛处理前$n^{\frac{2}{3}}$后,单次可以做到$O(n^{\frac{2}{3}})$

假设当前枚举到了$i$和素数$p_j$

若$i$是素数,则$\mu(i)=-1$

若$p_j \mid i$,设$i \times p_j=i’ \times p_j^k$,且$(i’,p_j^k)=1$,此时$k \ge 2$,则$\mu(i \times p_j)=\mu(i’) \times \mu(p_j^k)=0$

若$p_j \not \mid i \Rightarrow(i,p_j)=1$,则$\mu(i \times p_j)=\mu(i) \times \mu(p_j)=-\mu(i)$

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6;
ll n, phi[N + 10], mu[N + 10], pri[N + 10], tot, p[N + 10], q[N + 10];

bool vis[(int) 1e5 + 10];

ll getp(ll x) { return x <= N ? phi[x] : p[n / x]; }
ll getq(ll x) { return x <= N ? mu[x] : q[n / x]; }

void sol(ll x) {
if(x <= N || vis[n / x]) return ;
vis[n / x] = 1;
p[n / x] = (1 + x) * x / 2;
q[n / x] = x >= 1;
for(ll i = 2, j ; i <= x ; i = j + 1) {
j = x / (x / i);
sol(x / i);
p[n / x] -= getp(x / i) * (j - i + 1);
q[n / x] -= getq(x / i) * (j - i + 1);
}
}

int main() {
mu[1] = phi[1] = 1;
for(int i = 2 ; i <= N ; ++ i) {
if(!phi[i]) phi[i] = i - 1, mu[i] = -1, pri[++ tot] = i;
for(int j = 1 ; j <= tot && i * pri[j] <= N ; ++ j) {
if(i % pri[j] == 0) {
phi[i * pri[j]] = phi[i] * pri[j];
break;
} else {
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
mu[i * pri[j]] = -mu[i];
}
}
mu[i] += mu[i - 1];
phi[i] += phi[i - 1];
}
int T; scanf("%d", &T);
while(T --) {
scanf("%lld", &n);
memset(vis, 0, sizeof vis);
if(n <= N) printf("%lld %lld\n", phi[n], mu[n]);
else sol(n), printf("%lld %lld\n", p[1], q[1]);
}
}