SP19975 APS2 - Amazing Prime Sequence (hard)

· · 题解

前置知识：Min_25 筛。

默认读者已经掌握 Min_25 筛。

题意

给定 N，求：

\sum\limits_{i=2}^{N} \operatorname{lpf}(i).

其中 \operatorname{lpf}(n) 为 n 的最小质因数。规定 \operatorname{lpf}(1) = 1。

思路

分别考虑质数与合数的贡献。

质数的贡献为：

\sum\limits_{\substack{i \in [2,N] \\ \operatorname{isprime}(i)}} \operatorname{lpf}(i) = \sum\limits_{p \le N} \operatorname{lpf}(p) = \sum\limits_{p \le N} p.

令 g(p) = p，则质数的贡献为：

\sum\limits_{p \le N} g(p) = G_{\text{prime}}(N).

利用 Min_25 筛的第一部分即可求解。

合数的贡献为：

\sum\limits_{\substack{i \in [2,N] \\ \operatorname{isprime}(i)=0}} \operatorname{lpf}(i).

枚举所有可能的 p_k = \operatorname{lpf}(i)，则合数的贡献为：

\sum\limits_{\substack{k=1 \\ p_k^2 \le N}} p_k \left( \sum\limits_{i=2}^{N} [\operatorname{lpf}(i) = p_k \land i \neq p_k] \right).

令 g(p) = 1。

考虑 Min_25 筛第一部分中 G_k(N) 的递推式：

G_k(N) = G_{k-1}(N) - g(p_k)\left( G_{k-1}(N/p_k) - G_{\text{prime}}(p_{k-1}) \right).

注意到 g(p_k)\left( G_{k-1}(N/p_k) - G_{\text{prime}}(p_{k-1}) \right) 即为 \displaystyle\sum\limits_{i=1}^{N} [\operatorname{lpf}(i) = p_k \land i \neq p_k]。

在递推过程中统计贡献即可。

时间复杂度为 \mathcal{O}\left( \dfrac{N^{\frac{3}{4}}}{\log N} \right)。

Code

#include<bits/stdc++.h>
#define int unsigned long long

const int B=1.2e6+10;

using namespace std;

int T;

int n,b,ans;

int cnt,p[B];

bool vis[B];

int s1[B],s2[B];

int tot,w[B<<1];

int id1[B],id2[B];

int g1[B<<1],g2[B<<1];

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

int _sqrt(int x){
    int ret=floor(sqrtl(x));
    while((ret+1)*(ret+1)<=x)ret++;
    return ret;
}

int get_id(int _n){
    if(_n<=b)return id1[_n];
    return id2[n/_n];
}

int _sum(int _n){
    if(_n&1)return (_n+1)/2*_n;
    return _n/2*(_n+1);
}

void _init(){
    cnt=tot=0;
    for(int i=1;i<=b;i++)p[i]=vis[i]=s1[i]=s2[i]=id1[i]=id2[i]=0;
    for(int i=1;i<=b*2;i++)w[i]=g1[i]=g2[i]=0;
    for(int i=2;i<=b;i++){
        if(!vis[i]){
            p[++cnt]=i;
            s1[cnt]=s1[cnt-1]+1;
            s2[cnt]=s2[cnt-1]+i;
        }
        for(int j=1;j<=cnt&&i*p[j]<=b;j++){
            vis[i*p[j]]=1;
            if(!(i%p[j]))break;
        }
    }
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        int _n=n/l;
        w[++tot]=_n;
        if(_n<=b)id1[_n]=tot;
        else id2[n/_n]=tot;
        g1[tot]=_n-1;
        g2[tot]=_sum(_n)-1;
    }
    for(int k=1;k<=cnt;k++){
        for(int i=1;i<=tot&&p[k]*p[k]<=w[i];i++){
            int id=get_id(w[i]/p[k]);
            g1[i]-=g1[id]-s1[k-1];
            g2[i]-=p[k]*(g2[id]-s2[k-1]);
            if(i==1)ans+=p[k]*(g1[id]-s1[k-1]);
        }
    }
}

void _solve(){
    n=read();
    b=_sqrt(n);
    ans=0;
    _init();
    ans+=g2[1];
    printf("%llu\n",ans);
}

signed main(){
    T=read();
    while(T--)_solve();
    return 0;
}