自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:35:22，当前版本为作者最后更新于2022-09-17 11:42:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

• 原题链接

• 考虑到其余题解人均打表，这里来一篇不一样的做法。

• 当然正解是不可能正解的，那太人类智慧了，想学的请转 COCI 官网。

Part 1

• 首先我们可以发现，对于一个具体的询问，我们用 $L$ 和 $R$ 分别表示答案区间左右端点，那么可能的答案区间分为三种：

1. $R\leq M_i$：这种情况较为简单，只有 $K = L$ 且 $K \leq M_i$ 时才可能成立，$O(1)$ 判断即可。

2. $L\leq M_i,R>M_i$: 这种情况也不复杂，考虑到 $K$ 的范围，那么这样的区间最多不会超过 $150$ 个，直接暴力枚举判断即可。

3. $L>M_i$: 这就是本题的难点所在了，由于满足条件的区间过多，我们不可能一个个去试，那样的时间复杂度是 $10^{12}$，完全不可接受，接下来我们便一步一步去优化第三种情况。

Part 2

• 很自然地，我们想到了预处理，预处理出长度为 $k$ 的高兴数（因为是第三类情况，也可以说成质数）个数为 $L$ 的区间,询问时直接查表即可，这样做只需要对每一个区间长度扫一遍全集，时间复杂度能做到 $150 \times 10^7$，无疑优秀了许多。可这样做有一个限制是我们没有考虑到的，那就是 $M$。
• 怎样才能忽略 $M$ 的限制呢？考虑贪心，对于满足长度为 $i$，区间内质数个数为 $j$ 的区间，我们只保留起始位置最大的那个。这是因为 $M$ 对答案的限制只是区间左端点必须大于 $M$，那左端点当然是越大越好！
• 于是，我们成功地完成了优化地第一步。

Part 3

• 在进入最重要的优化前，先讲几个更容易想到，但似乎用处不太大的 trick：

1. 只预处理询问中出现过的区间长度。
2. 预处理时倒序查找，如果对当前 $K$ 值，所以合法的 $L$ 都找到了区间，则中断循坏。
3. 各种常数优化。

Part 4

• 其实若是这道题时限给到 $2 s$，那本篇题解也就到此为止了，可惜呀！
• 当我们发现其余地方都做到了极致时，似乎忘记考虑一个被我们忽略的细节：那就是我们真的需要 $10^7$ 的全集吗？
• 让我们思考一下，对于确定的 $K$ 值，$L$ 能否取到只关乎与区间质数密度，而质数密度的范围与全集大小的关系并不是完全对应的，有没有这样一种可能，用更小的全集规模就能筛出 $10^7$ 所能筛出的所有 $L$ 的取值？
• 这时，你就可以愉快地人肉二分了！！！（正好正解也是二分）
• 这里直接放结论，$3\times 10^6$ 就足够了。

• 于是，你愉快地通过了此题。
• 代码：

#include<bits/stdc++.h>
using namespace std;

const int N=3e6,M=5e5+10,G=155;
int Q,k,l,m;
int v[N],prime[M],id,ans[G][G];
bool st[G];

inline int read()
{
	int x=0;char ch=getchar();
	while(!isdigit(ch))	ch=getchar();
	while(isdigit(ch))	x=x*10+ch-'0',ch=getchar();
	return x;
}
inline void write(int x)
{
	if(!x)	return;
	write(x/10);
	putchar(x%10+'0');
}
inline void init()
{
	for(register int i=2;i<=N-10;i++)
	{
		if(!v[i])	v[i]=i,prime[++id]=i;
		for(int j=1;j<=id;j++)
		{
			if(i*prime[j]>N-10||prime[j]>v[i])	break;
			v[i*prime[j]]=prime[j];
		}
	}
  	 //欧拉筛筛质数
	for(register int i=1;i<=N-10;i++)	v[i]=v[i-1]+(v[i]==i);
  	 //质数前缀和
}
inline void get(int len)
{
	int cnt=0;
	for(register int sta=N-160;sta>=1;sta--)
	{
		if(ans[len][v[sta+len-1]-v[sta-1]])	continue;
		cnt++;
		ans[len][v[sta+len-1]-v[sta-1]]=sta;
		if(cnt==len+1)	break;
	}	
	//对每一个 k 值进行预处理
}
int main()
{
	init();
	Q=read();
	for(register int i=1;i<=Q;i++)
	{
		k=read(),l=read(),m=read();
		if(k==l&&k<=m)
		{
			putchar('1');
			putchar('\n');
			continue;	
		}
		//情况一
		bool flag=false;
		for(register int j=max(1,m-k+2);j<=m;j++)	
			if(m-j+1+v[j+k-1]-v[m]==l)
			{
				write(j);
				putchar('\n');
				flag=true;
				break;
			}
		if(flag)	continue;
		//情况二
		if(!st[k])	st[k]=true,get(k);
		if(ans[k][l]>m)	
		{
			write(ans[k][l]);
			putchar('\n');
		}
		//情况三
		else
		{
			putchar('-');
			putchar('1');
			putchar('\n');
		}
		//无解
	}
	return 0;
}

• 完结撒花~