自动搬运

查看原文

来自洛谷，原作者为

	World_Creater 事蠢脸 || 个人博客 worldcreaterwc.github.io

搬运于2025-08-24 22:48:05，当前版本为作者最后更新于2023-06-28 21:06:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 $n$ 小的时候怎么做。

直接预处理出 $n$ 以内的所有质数，做一个前缀和，然后双指针即可，这一部分是简单的，复杂度 $\mathcal{O}(n)$。

当 $n$ 大时这样显然寄了，考虑用这种做法做到上限为 $L$，即解决所有答案右端点在 $[1,L]$ 内的情况，这个时候，答案右端点显然在 $(L,n]$ 内，不难发现，满足如上情况时答案的质数个数只有 $\mathcal{O}(\dfrac{n}{L})$ 级别。

考虑枚举质数个数，设现在枚举的质数个数为 $t$，则答案肯定在 $\dfrac{n}{t}$ 附近，设答案区间的左右端点落在 $[l',r']$ 内，由素数密度我们可以知道，$r'-l'=\mathcal{O}(t\ln n)$。因此我们暴力的范围最终很小，像上面那样再做双指针即可。

时间复杂度 $\mathcal{O}(L+\dfrac{n^2}{L^2}\ln n\operatorname{check}(n))$，其中 $\operatorname{check}(n)$ 为检验一个大数 $n$ 是否为质数的复杂度，假如我们用米勒拉宾算法来求质数，那么取 $L=n^{\frac{2}{3}}\log n$ 可以做到复杂度 $\mathcal{O}({n^\frac{2}{3}\log n})$（这里让 $\ln n$ 和 $\log n$ 同级）。

当然数字较大的时候一个一个判素数还是太笨蛋了，因为最终的暴力区间不会很大，因此可以考虑使用筛区间质数的方法，即：假如我们要筛 $[l,r]$ 内的质数，我们枚举 $\sqrt{r}$ 内的质数去更新当前区间的质数信息，显然枚举的质数个数不会很多。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,pre[5000005],prp[5000005],cnt;
bitset<100000005> f;
bitset<200005> chk;
void solve(int l,int r)
{
	chk.reset();
	// memset(chk,0,sizeof(chk));
	for(int i=1;i<=cnt&&prp[i]*prp[i]<=r;i++)
	{
		// cerr<<"????"<<i<<"\n";
		for(int j=(l+(prp[i]-1))/prp[i];j*prp[i]<=r;j++)
		{
			// cerr<<j*prp[i]<<"\n";
			chk[prp[i]*j-l]=1;
		}
	}
}
int findnxt(int x,int g)
{
	int i=x+1;
	while(chk[i-g]) i++;
	return i;
}
int findpre(int x,int g)
{
	int i=x-1;
	while(i>=2&&chk[i-g]) i--;
	return i;
}
bool check(int n)
{
	if(n==1) return 0; 
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) return 0;
	}
	return 1;
}
signed main()
{
	cin>>n;
	for(int i=2;i<=20000000&&i<=n;i++)
	{
		if(!f[i]) prp[++cnt]=i;
		for(int j=1;j<=cnt&&i*prp[j]<=20000000&&i<=n;j++)
		{
			f[i*prp[j]]=1;
			if(i%prp[j]==0) break ;
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		pre[i]=pre[i-1]+prp[i];
	}
	int l=1;
	if(n==1)
	{
		cout<<"NIE";
		return 0;
	}
	if(check(n))
	{
		cout<<n<<" "<<n;
		return 0;
	}
	for(int i=1;i<=cnt;i++)
	{
		while(l<i&&pre[i]-pre[l-1]>n) l++;
		if(pre[i]-pre[l-1]==n)
		{
			cout<<prp[l]<<" "<<prp[i]<<"\n";
			return 0;
		}
	}
	for(int i=2;i<=5000;i++)
	{
		int t=n/i;
		int base=20;
		if(i<=5) base=200;
		int LIM=max(t-max(i*base,100000ll),1ll);
		solve(LIM,t+max(i*base,100000ll));
		int r=findnxt(t,LIM);
		vector<int> pp;
		pp.emplace_back(r);
		if(r<=2e7) break ;
		int sum=r,cnt=1,l=r,it=0;
		while(cnt<i) l=findpre(l,LIM),sum+=l,cnt++,pp.emplace_back(l);
		// cerr<<"???"<<t<<" "<<l<<" "<<r<<"\n";
		reverse(pp.begin(),pp.end());
		while(sum<n) sum-=l,l=pp[++it],r=findnxt(r,LIM),sum+=r,pp.emplace_back(r);
		if(sum==n)
		{
			cout<<l<<" "<<r;
			cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC;
			return 0;
		} 
	}
	cout<<"NIE";
}