专栏文章

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

ggcx12012
P13360题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miosojwl
此快照首次捕获于
2025/12/03 00:30
3 个月前
此快照最后确认于
2025/12/03 00:30
3 个月前
查看原文
由于主播不会 min25 筛，这里提供一个分块打表的做法。
首先不难发现只有 >n2>\frac{n}{2} 的质数是孤立点，其它的点都是连通的，于是和的平方减去平方和处理即可。
首先一个非质数的最小质因子 ≤V\le \sqrt V，于是预处理出 V\sqrt V 内的质数就可以筛掉一段区间。
然后就随便设置块长即可，注意一下洛谷代码提交长度限制是 50k，这里设置块长为 5×1075\times 10^7，除了最后一个点都跑的飞快。
参考代码：
CPP
#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;
}
/*
*/
打表的代码：
CPP
#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;
}
/*
*/

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...