bzoj 3944 Sum —— 杜教筛

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3944

杜教筛入门题！

看博客：https://www.cnblogs.com/zjp-shadow/p/8491542.html

写法模仿其他博客的，但很慢啊...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

typedef long long ll;

int const maxn=;

ll T,m,p[maxn],phi[maxn],mu[maxn],cnt,mx;

bool vis[maxn];

map<ll,ll>mp1,mp2;

ll rd()

{

    ll ret=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

    while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return ret*f;

}

void init()

{

    int n=mx;

    phi[]=; mu[]=;

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

    {

        if(!vis[i])phi[i]=i-,p[++cnt]=i,mu[i]=-,vis[i]=;

        for(int j=;j<=cnt&&i*p[j]<=n;j++)

        {

            vis[i*p[j]]=;

            if(i%p[j]==)

            {

                phi[i*p[j]]=phi[i]*p[j]; mu[i*p[j]]=;

                break;

            }

            phi[i*p[j]]=phi[i]*(p[j]-);

            mu[i*p[j]]=-mu[i];

        }

    }

    for(int i=;i<=n;i++)mu[i]+=mu[i-],phi[i]+=phi[i-];

}

void dfs(ll n,ll &ans1,ll &ans2)

{

    if(n<mx){ans1=phi[n]; ans2=mu[n]; return;}

    if(mp1.count(n)){ans1=mp1[n]; ans2=mp2[n]; return;}

    ans1=(n+)*n/; ans2=;

    for(ll i=,lst;i<=n;i=lst+)

    {

        lst=n/(n/i);// i ~ n/(n/i) 答案都相同

        ll tmp1,tmp2; dfs(n/i,tmp1,tmp2);

        ans1-=tmp1*(lst-i+);

        ans2-=tmp2*(lst-i+);

    }

    mp1[n]=ans1; mp2[n]=ans2;

}

int main()

{

    mx=;

    init();

    T=rd();

    while(T--)

    {

        m=rd();

        ll ans1,ans2; dfs(m,ans1,ans2);

        printf("%lld %lld\n",ans1,ans2);

    }

    return ;

}