题目

传送门

思路

杜教筛的板子，拿来练手

pace1

\[\begin{aligned}ans&=\sum_{i=1}^{n}\phi(i)\\\end{aligned}\\g(n)=1,\phi(n)=f(n)\\h(n)=\sum_{d|n}\phi(d)*g(\frac{n}{d})=n\\ \]

\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d})\\令F(n)=\sum_{i=1}^{n}f(i),H(n)=\sum_{i=1}^{n}h(i)\\\begin{aligned}H(n)&=\sum_{i=1}^{n}h(i)\\&=\sum_{i=1}^{n}\sum_{d|i}f(d)*g(\frac{i}{d})\\&=\sum_{i=1}^{n}\sum_{d|i}f(\frac{i}{d})g(d)\\&=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\&=\sum_{d=1}^{n}g(d)F(\lfloor\frac{n}{d}\rfloor)\\&=g(1)F(n)+\sum_{d=2}^{n}g(d)F(\lfloor\frac{n}{d}\rfloor)\end{aligned} \]

\[F(n)=\frac{H(n)-\sum_{d=2}^{n}g(d)F(\lfloor\frac{n}{d}\rfloor)}{g(1)} \]

其中\(H(n)\)的时间复杂度为\(O(1)\)，\(g(d)\)也为\(O(1)\)，对\(\sum_{d=2}^ng(d)F(\lfloor\frac{n}{d}\rfloor)\)数论分块就好了

时间复杂度\(O(n^{\frac{2}{3}})\)

pace2

\[ans=\sum_{i=1}^{n}\mu(i) \]

\[设f(i)=\mu(i),g(i)=1,那么显然h(i)=(f*g)(i)=[i=1]\\设F(i)=\sum_{i=1}^nf(i),H(i)=\sum_{i=1}^{n}h(i) \]

\[\begin{aligned}H(i)&=\sum_{i=1}^nh(i)\\&=\sum_{i=1}^n\sum_{d|i}f(\frac{i}{d})g(d)\\&=\sum_{d=1}^ng(d)F(\lfloor\frac{n}{d}\rfloor)\\&=g(1)F(n)+\sum_{d=2}^ng(d)F(\lfloor\frac{n}{d}\rfloor)\end{aligned} \]

\[F(n)=\frac{H(i)-\sum_{d=2}^ng(d)F(\lfloor\frac{n}{d}\rfloor)}{g(1)} \]

一样的，时间复杂度为$O(n^{\frac{2}{3}}) $

代码

#include<unordered_map>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int T;
int n;
int len;
int phi[2000005],mu[2000005];
int lenp,pri[2000005];
bool vis[2000005];
long long mphi[2000005];
long long mmu[2000005];
unordered_map<int,long long> m1;
unordered_map<int,long long> m2;
void prepa(int n)
{
    len=n;
    mphi[1]=1;
    mmu[1]=mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(vis[i]==0)
        {
            pri[++lenp]=i;
            phi[i]=i-1;mu[i]=-1;
        }
        for(int j=1;j<=lenp&&1ll*pri[j]*i<=n;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                mu[i*pri[j]]=0;
                phi[i*pri[j]]=pri[j]*phi[i];
                break;
            }
            mu[i*pri[j]]=mu[i]*mu[pri[j]];
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
        mmu[i]=mmu[i-1]+mu[i];
        mphi[i]=mphi[i-1]+phi[i];
    }
}
long long getphi(long long n)
{
    if(n<=len)
        return mphi[n];
    if(m1.count(n))
        return m1[n];
    long long temp=1ll*n*(n+1)/2;
    for(long long l=2,r;l<=n;l=r+1)
    {
        r=min(1ll*n/(n/l),1ll*n);
        temp=temp-1ll*(r-l+1)*getphi(n/l);
    }
    return m1[n]=temp;
}
long long getmu(int n)
{
    if(n<=len)
        return mmu[n];
    if(m2.count(n))
        return m2[n];
    long long temp=1;
    for(long long l=2,r;l<=n;l=r+1)
    {
        r=min(1ll*n/(n/l),1ll*n);
        temp=temp-1ll*(r-l+1)*getmu(n/l);
    }
    return m2[n]=temp;
}
void c_in()
{
    cin>>n;
    cout<<getphi(n)<<' '<<getmu(n)<<'\n';
}
int main()
{
    prepa(pow((1ll<<31)-1,2.0/3));
    cin>>T;
    for(int i=1;i<=T;i++)
        c_in();
    return 0;
}