杜教筛习题：bzoj 3944 sum

题目描述

给定正整数$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)$

代码

#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]);
    }
}