自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:16:54，当前版本为作者最后更新于2020-02-06 15:43:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Update on 2020.5.11

bitset 优化筛法。

首先 $10^7$ 组询问，肯定要预处理出范围内的所有素数然后 $O(1)$ 判断。

线性筛会爆空间（似乎也能过？），只能用埃氏筛。

先筛掉 $2,3$ 的倍数，然后在 $6$ 个里面只用筛 $2$ 个：$i(6i+1)$，$i(6i+5)$。

用 bitset 压一下位就行了。注意不需要筛偶数，可大大减少时间和空间。

std：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int k=1,s[10005],prime[10005];
bitset<50110005>vst;
inline bool Prime(register int n){
	return n<2?0:(n==2?1:(n%2&&!vst[n>>1]));
}
int main() {
//	freopen("5.in","r",stdin);
//	freopen("5.out","w",stdout);
	for(int i=9; i<=100030000; i+=6)vst[i>>1]=1;
	for(int i=15; i<=100030000; i+=10)vst[i>>1]=1;
	for(register int i=7; i<=20000; i+=2){
		if(vst[i>>1])continue;
		for(register int j=i*(i/6*6+1); j<=100030000; j+=i*6){
			vst[j>>1]=1;
            vst[(j>>1)+(i<<1)]=1;
		}
	}
	int T,x0,y0,s=0;
	scanf("%d%d%d",&T,&x0,&y0);
	while(T--){
		x0=((7*x0+13)^(x0/13-7));
		y0=((7*y0+13)^(y0/13-7));
		int x=(x0%10000+10000)%10000+1,y=(y0%10000+10000)%10000+1;
		if(Prime(x)&&Prime(y)&&Prime(x*y-3*(x-y)))s++;
	}
	cout<<s;
	return 0;
}