P4213 【模板】杜教筛

[题目链接] https://www.luogu.org/problemnew/show/P4213

给定一个正整数\(N(N\le2^{31}-1)\)

求

\(ans_1=\sum_{i=1}^n\varphi(i)\)

\(ans_2=\sum_{i=1}^n \mu(i)\)

[题解] https://acfcacfca.blog.luogu.org/dls-tql

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#include<tr1/unordered_map>

//#define int long long

using namespace std;

typedef long long LL;

const int INF=1e9+7;

inline LL read(){

    register LL x=0,f=1;register char c=getchar();

    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

    return f*x;

}

const int MAXN=5e6+5;

LL mu[MAXN];LL phi[MAXN];

int prime[MAXN];bool vis[MAXN];

unordered_map <int,LL> Smu,Sphi;

int n,T;

inline void init(int n){

    mu[1]=1,phi[1]=1;

    for(int i=2;i<=n;i++){

        if(!vis[i]){

            prime[++prime[0]]=i;

            mu[i]=-1;

            phi[i]=i-1;

        }

        int x;

        for(int j=1;j<=prime[0]&&(x=(i*prime[j]))<=n;j++){

            vis[x]=1;

            if(i%prime[j]==0){

                mu[x]=0;

                phi[x]=1ll*phi[i]*prime[j];

                break;

            }

            mu[x]=-mu[i];

            phi[x]=1ll*phi[i]*phi[prime[j]];

        }

    }

    for(int i=2;i<=n;i++)

        mu[i]+=mu[i-1],phi[i]+=phi[i-1];

}

inline LL S_mu(int x){

    if(x<MAXN) return mu[x];

    if(Smu[x]) return Smu[x];

    LL res=1;

    for(int l=2,r;l<=x;l=r+1){

        r=x/(x/l);

        res-=1ll*(r-l+1)*S_mu(x/l);

    }

    return Smu[x]=res;

}

inline LL S_phi(int x){

    if(x<MAXN) return phi[x];

    if(Sphi[x]) return Sphi[x];

    LL res=1LL*x*(x+1)/2;//对int敏感!!

    for(int l=2,r;l<=x;l=r+1){

        r=x/(x/l);

        res-=1LL*(r-l+1)*S_phi(x/l);

    }

    return Sphi[x]=res;

}

signed main(){

    T=read();

    init(MAXN-1);

    while(T--){

        n=read();

        printf("%lld %lld\n",S_phi(n),S_mu(n));

    }

}

巴特西

P4213 【模板】杜教筛

最新文章

热门文章