杜教筛【莫比乌斯前缀和，欧拉函数前缀和】推导与模板【一千五百字】

下图给出杜教筛详细推导过程，前置知识有积性函数和莫比乌斯反演。

杜教筛是一种优秀的求积性函数前缀和算法，其时间复杂度受预处理数组的影响，一般开到2/3次幂大小，可使复杂度达到较为优秀的程度。

 

杜教筛的时间复杂度还要取决于预处理数组的大小，将预处理前缀和数组处理到n^(2/3)大小会使杜教筛时间复杂度缩短至 O(n^(2/3)) ，否则会超时

 【模板】杜教筛（Sum） - 洛谷

# include<iostream>
# include<map>
# include<unordered_map>
# include<math.h>
using namespace std;
typedef long long int ll;

unordered_map<int,int>m;


const int N=1664503;

int tot;
int prime[N+10];
ll mu[N+10];
bool not_prime[N+10];
ll phi[N+10];
unordered_map<ll,ll>sum_mu;
unordered_map<ll,ll>sum_phi;

inline void init(int n)
{
    mu[1]=1;
    phi[1]=1;

    for(ll i=2; i<=n; i++)
    {
        if(!not_prime[i])
        {

            tot++;

            prime[tot]=i;

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

        }

        for(ll j=1; j<=tot&&i*prime[j]<=N; j++)
        {
            not_prime[i*prime[j]]=1;

            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;

            }
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*(prime[j]-1);

        }
    }
    for(int i=1;i<=n;i++)
    {
        mu[i]+=mu[i-1];
        phi[i]+=phi[i-1];

    }
}

inline int  g_sum(int  x)
{
    return x;

}

inline int   getsum_mu(int  x)
{

    if(x<=N)
        return mu[x];

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

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

        r=x/(x/l);

        ans-=(g_sum(r)-g_sum(l-1))*getsum_mu(x/l);

    }

    return sum_mu[x]=ans/g_sum(1ll);

}
inline ll getsum_phi(ll  x)
{
    if(x<=N)
        return phi[x];

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

    ll ans=(ll)x*(ll)(x+1)/2;

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

        ans-=(g_sum(r)-g_sum(l-1))*getsum_phi(x/l);

    }

    return sum_phi[x]=ans/g_sum(1ll);
}
int main ()
{



   init(N);

   int t;

   cin>>t;

   while(t--)
   {
       ll n;

       cin>>n;

       cout<<getsum_phi(n)<<" "<<getsum_mu(n)<<'\n';
   }


    return 0;

}