[BZOJ 4176]Lucas的数论

Link

Solution

比较套路地画出来

\sum_{d}\mu(d)F([\frac nd])^2

其中

F(n)=\sum_{i=1}^n[\frac ni]

主要是求F函数部分的复杂度如何估计

\begin{aligned}
T(n)\approx&\sum_{d=1}^{\sqrt n}(\sqrt d+\sqrt{\frac nd})\\
\approx&\int_{1}^{\sqrt n}(\sqrt x+\sqrt {\frac nx}){\rm d}x\\
=&(2(nx)^{\frac 12}+\frac {2x^{\frac 32}}3)\bigg|_1^{\sqrt n}\\
=&O(n^{\frac 34})
\end{aligned}

Code

const int P=1000000007,N=1e6,XN=N+11;

int prime[XN],mu[XN],pcnt,smu[XN];
void Prep() {
    static bool notPrime[XN];
    mu[1]=1;
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0) {
                mu[i*prime[j]]=0;
                break;
            } else
                mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=N;++i)
        smu[i]=smu[i-1]+mu[i];
}

int Smu(int n) {
    if(n<=N)
        return smu[n];
    else {
        static std::unordered_map<int,int> map;
        if(map.count(n))
            return map[n];
        long long res=1;
        for(int l=2,r;l<=n;l=r+1) {
            r=n/(n/l);
            (res-=(long long)(r-l+1)*Smu(n/l))%=P;
        }
        return map[n]=res;
    }
}

int F(int n) {
    long long res=0;
    for(int l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        (res+=(long long)(r-l+1)*(n/l))%=P;
    }
    return res;
}

int main() {
    Prep();
    int n;fin>>n;
    long long Ans=0;
    for(int l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        long long x=F(n/l);
        (x*=x)%=P;
        (Ans+=(long long)(Smu(r)-Smu(l-1))*x)%=P;
    }
    Ans<0 && (Ans+=P);
    fout<<Ans<<'\n';
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注