【BZOJ4916】神犇和蒟蒻 解题报告

【BZOJ4916】神犇和蒟蒻

Description

很久很久以前，有一群神犇叫sk和ypl和ssr和hjh和hgr和gjs和yay和xj和zwl和dcx和lyy和dtz和hy和xfz和myh和yww和zjt;

很久很久之后，有一只蒟蒻叫ypl，被神犇myh的做题记录碾在地上;

Input

​ 请你读入一个整\(N\);

Output

​ 请你输出一个整数\(A=\sum_{i=1}^n\mu(i^2);(\bmod1000000007)\)

​ 请你输出一个整数\(B=\sum_{i=1}^n\varphi(i^2);(\bmod 1000000007)\)

HINT

\(1≤N≤10^9\)

---

杜教筛板子，复习了一下...

显然\(A=1\)

然后\(\varphi(i^2)=i\varphi(i)\)，因为不改变质因子的种类，所以可以直接乘出来。

设\(\mathtt f=i\varphi(i)\)，那么

\[\mathtt {Id^2}=\mathtt f * \mathtt{Id}
\]

于是直接杜教筛就行了

---

Code:

#include <cstdio>

#include <unordered_map>

#define ll long long

std::unordered_map <int,ll> F;

const int N=1e6;

const ll mod=1e9+7;

int pri[N+10],ispri[N+10],cnt;

ll f[N+10];

void init()

{

    f[1]=1;

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

    {

        if(!ispri[i])

        {

            pri[++cnt]=i;

            f[i]=i-1;

        }

        for(int j=1;j<=cnt&&pri[j]*i<=N;j++)

        {

            ispri[i*pri[j]]=1;

            if(i%pri[j]==0)

            {

                f[i*pri[j]]=f[i]*pri[j];

                break;

            }

            f[i*pri[j]]=f[i]*(pri[j]-1);

        }

    }

    for(int i=1;i<=N;i++) f[i]=(f[i]*i+f[i-1])%mod;

}

#define g(a) (1ll*(a)*(a+1)/2)

const ll inv=166666668;

ll Sum(int n)

{

    if(n<=N) return f[n];

    if(F.find(n)!=F.end()) return F[n];

    ll ret=1ll*n*(n<<1|1)%mod*(n+1)%mod*inv%mod;

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

    {

        r=n/(n/l);

        (ret-=(g(r)-g(l-1))*Sum(n/l))%=mod;

    }

    return F[n]=((ret+mod)%mod);

}

int main()

{

    init();

    int n;scanf("%d",&n);

    printf("1\n%lld",Sum(n));

    return 0;

}

---

2018.12.16