P2568 莫比乌斯反演+整除分块

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn=1e7+;

bool vis[maxn];

int prime[maxn];

int mu[maxn];

int sum1[maxn];

int sum2[maxn];

int tot=;

void get_mu()// mo bi su si han shu

{

    mu[]=;  vis[]=;

    for(int i=;i<maxn;i++)  // prime = 0;  other = 1;

    {

        if(!vis[i]){ prime[++tot]=i; mu[i]=-;}

        for(int j=;j<=tot&& prime[j]*i<maxn;j++)

        {

            vis[prime[j]*i]=;

            if(i%prime[j]==)break;

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

        }

    }

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

    {

        for(int j=prime[i];j<maxn;j+=prime[i])

        {

            sum1[j]+=mu[j/prime[i]];

        }

    }

    //for(int i=1;i<maxn;i++)  sum2[i]=sum2[i-1]+sum1[i];

}

int main()

{

    get_mu();

    int n; cin>>n;

    LL ans=;

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

    {

        ans+=1LL*(n/i)*(n/i)*sum1[i];

    }

    cout<<ans<<endl;

}

过度代码

整除分块  (看起来更麻烦)

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn=1e7+;

bool vis[maxn];

int prime[maxn];

int mu[maxn];

int sum1[maxn];

int sum2[maxn];

int tot=;

void get_mu()// mo bi su si han shu

{

    mu[]=;  vis[]=;

    for(int i=;i<maxn;i++)  // prime = 0;  other = 1;

    {

        if(!vis[i]){ prime[++tot]=i; mu[i]=-;}

        for(int j=;j<=tot&& prime[j]*i<maxn;j++)

        {

            vis[prime[j]*i]=;

            if(i%prime[j]==)break;

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

        }

    }

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

    {

        for(int j=prime[i];j<maxn;j+=prime[i])

        {

            sum1[j]+=mu[j/prime[i]];

        }

    }

    for(int i=;i<maxn;i++)  sum2[i]=sum2[i-]+sum1[i];

}

int main()

{

    get_mu();

    int n; cin>>n;

    LL ans=;

    //for(int i=1;i<=n;i++)  ans+=1LL*(n/i)*(n/i)*sum1[i];

    for(int l=,r;l<=n;l=r+)

    {

        r=n/(n/l);  //  l-r 区间相同值  区间值n/l

        ans+=1LL*(n/l)*(n/l)*(sum2[r]-sum2[l-]);

    }

    cout<<ans<<endl;

}