题解：P13360 [GDCPC 2024] 另一个计数问题

· · 题解

由于主播不会 min25 筛，这里提供一个分块打表的做法。

首先不难发现只有 >\frac{n}{2} 的质数是孤立点，其它的点都是连通的，于是和的平方减去平方和处理即可。

首先一个非质数的最小质因子 \le \sqrt V，于是预处理出 \sqrt V 内的质数就可以筛掉一段区间。

然后就随便设置块长即可，注意一下洛谷代码提交长度限制是 50k，这里设置块长为 5\times 10^7，除了最后一个点都跑的飞快。

参考代码：

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ld long double
#define ull unsigned long long
#define lll __int128
#define N 400010
#define For(i,a,b) for(ll i=a;i<=b;++i)
#define Rof(i,a,b) for(ll i=a;i>=b;--i)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mk make_pair
#define pb push_back
#define pii pair<ll,ll>
#define pque priority_queue
#define fi first
#define se second

using namespace std;
const ll B=50000000;
ll s1[2010]={略};
ll s2[2010]={略};
ll is[N],pri[N],cnt=0,n; 

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const ll mod=998244353;
bool vis[50000010];
ll get2(ll L,ll R){
    if(L>R) return 0;
    memset(vis,0,sizeof(vis));
    For(i,1,cnt){
        for(ll j=max(2ll,(L-1)/pri[i]+1)*pri[i];j<=R;j+=pri[i]) vis[j-L]=1;
    }
    ll sum=0;
    For(i,L,R) if(!vis[i-L]) sum=(sum+(i%mod)*(i%mod)%mod)%mod;
    if(L==1) sum--;
    return sum;
}
ll get1(ll L,ll R){
    if(L>R) return 0;
    memset(vis,0,sizeof(vis));
    For(i,1,cnt){
        for(ll j=max(2ll,(L-1)/pri[i]+1)*pri[i];j<=R;j+=pri[i]) vis[j-L]=1;
    }
    ll sum=0;
    For(i,L,R) if(!vis[i-L]) sum=(sum+i)%mod;
    if(L==1) sum--;
    return sum;
}
lll calc1(lll x){
    return (x*(x+1)/2-1)%mod;
}
lll calc2(lll x){
    return (x*(x+1)*(2*x+1)/6-1)%mod;
}

int main()
{
    //freopen("card.in","r",stdin);
    //freopen("card.out","w",stdout);
    For(i,2,N-1){
        if(!is[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt && pri[j]*i<N;++j){
            is[pri[j]*i]=1; 
            if(i%pri[j]==0) break;
        }
    }
    n=read();
    ll L=n/2+1,R=n;
    ll p1=(L-1)/B,p2=(R-1)/B;
    ll sum1=calc1(n),sum2=calc2(n);
    if(p1==p2){
        sum1=(sum1-get1(L,R)+mod)%mod;
        sum2=(sum2-get2(L,R)+mod)%mod;
    }else{
        sum1=(sum1-get1(L,p1*B+B)-get1(p2*B+1,R)+mod+mod)%mod;
        sum2=(sum2-get2(L,p1*B+B)-get2(p2*B+1,R)+mod+mod)%mod;
        For(i,p1+1,p2-1) sum1=(sum1-s1[i]+mod)%mod;
        For(i,p1+1,p2-1) sum2=(sum2-s2[i]+mod)%mod;
    }
    sum1=(sum1*sum1%mod-sum2+mod)%mod;
    sum1=sum1*(mod+1)/2;
    cout<<sum1%mod;
    return 0;
}
/*
*/

打表的代码：

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ld long double
#define ull unsigned long long
#define lll __int128
#define N 400010
#define For(i,a,b) for(ll i=a;i<=b;++i)
#define Rof(i,a,b) for(ll i=a;i>=b;--i)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mk make_pair
#define pb push_back
#define pii pair<ll,ll>
#define pque priority_queue
#define fi first
#define se second

using namespace std;
const ll B=50000000;
ll s1[2010]={};
ll s2[2010]={};
ll is[N],pri[N],cnt=0,n; 

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const ll mod=998244353;
bool vis[50000010];
ll get2(ll L,ll R){
    if(L>R) return 0;
    memset(vis,0,sizeof(vis));
    For(i,1,cnt){
        for(ll j=max(2ll,(L-1)/pri[i]+1)*pri[i];j<=R;j+=pri[i]) vis[j-L]=1;
    }
    ll sum=0;
    For(i,L,R) if(!vis[i-L]) sum=(sum+(i%mod)*(i%mod)%mod)%mod;
    if(L==1) sum--;
    return sum;
}
ll get1(ll L,ll R){
    if(L>R) return 0;
    memset(vis,0,sizeof(vis));
    For(i,1,cnt){
        for(ll j=max(2ll,(L-1)/pri[i]+1)*pri[i];j<=R;j+=pri[i]) vis[j-L]=1;
    }
    ll sum=0;
    For(i,L,R) if(!vis[i-L]) sum=(sum+i)%mod;
    if(L==1) sum--;
    return sum;
}

int main()
{
    //freopen("card.in","r",stdin);
    //freopen("card.out","w",stdout);
    For(i,2,N-1){
        if(!is[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt && pri[j]*i<N;++j){
            is[pri[j]*i]=1; 
            if(i%pri[j]==0) break;
        }
    }
    for(ll L=1,R;L<=1e11;L+=B){
        R=L+B-1;
        s1[L/B]=get1(L,R);
        s2[L/B]=get2(L,R);
        //cout<<s1[L/B]<<' '<<s2[L/B]<<endl;
    }
    return 0;
}
/*
*/