自动搬运

查看原文

来自洛谷，原作者为

	王熙文 **

搬运于2025-08-24 22:31:19，当前版本为作者最后更新于2021-05-07 21:04:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

前置知识：欧拉筛

思路：

$1.$ 先筛出 $1 \sim 10^8$ 的所有素数，用欧拉筛。有一个问题，用普通的 bool 数组标记素数 or 合数空间会爆，那么可以用 STL 里的 bitset。定义写 bitset<100000001> b; 其它的和 bool 数组差不多，但空间是 bool 数组的 $\dfrac{1}{8}$。

$2.$ 从小到大枚举每个筛好的素数，求出各位数字和，由于塔小于等于 $9 \times 8 = 72$，所以可以直接用枚举判断。如果是双重素数，那么放到答案数组储存。

$3.$ 对于每次输入，我们需要找到答案数组中第一个严格大于 $r$ 的数的位置与第一个大于等于 $r$ 的数的位置。因为答案数组是递增的（因为 $2.$ 是从小到大枚举的），于是可以用二分快速找到位置。

有两个很好用的函数：lower_bound 和 upper_bound，lower 是找到一个递增数组里第一个大于等于某数的位置，upper 是找到一个递增数组里第一个大于某数的位置（你没看错，只差一个等于）。

它们的用法（找到位置）：lower_bound/upper_bound(a+1,a+n+1,x)-a。

这里 $a$ 是要寻找的递增数组，$n$ 是这个数组的长度，$x$ 是要找到的数（上文中的“某数”）。这样写是数组存数 $1 \sim n$ 的，如果数组存数是 $0 \sim n-1$，那么把两个 +1 删掉即可。

那么输出就是 upper_bound(ans+1,ans+k+1,r)-ans-(lower_bound(ans+1,ans+k+1,l)-ans)。

这是我的代码：

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

inline bool sushu(int a) { // 暴力判断数字和是否为素数 
	if(a==43 || a==47 || a==53 || a==59 || a==61 || a==67 || a==71) {
		return 1;
	}
	if(a==41 || a==37 || a==31 || a==29 || a==23 || a==19 || a==17 || a==13 || a==11 || a==7 || a==5 || a==3 || a==2) {
		return 1;
	}
	return 0;
} 

int dp[10000010]; // double prime
bitset<100000001> b;
int ans[10000010];
int k=0;
void work() { // 欧拉筛 + 筛出双重素数 
	const int n=100000000;
	b[1]=1;
	for(int i=2; i<=n; ++i) {
		if(!b[i]) {
			dp[++k]=i;
		}
		for(int j=1; j<=k && i*dp[j]<=n; ++j) {
			b[dp[j]*i]=1;
			if(!(i%dp[j])) {
				break;
			}
		}
	}
	int k1=k;
	k=0;
	for(int i=1; i<=k1; ++i) {
		int sum=0,t=dp[i];
		while(t) {
			sum+=t%10;
			t/=10;
		}
		if(sushu(sum)) {
			ans[++k]=dp[i];
		}
	}
}

int main() {
	work();
	int t,l,r;
	cin>>t;
	for(; t; --t) {
		cin>>l>>r;
		cout<<upper_bound(ans+1,ans+k+1,r)-ans-(lower_bound(ans+1,ans+k+1,l)-ans)<<endl;
	}
	return 0;
}

另外，我发明了一种方式存储 bool 数组值，时间和空间都和 bitset 差不多，详见我的这篇 blog。下面是我的用这种方式做的代码：

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

const int Size=100000000;

unsigned int B[(Size+32+1)>>5];

inline void change(int wz,int turn) {
    int add=wz&31;
    wz>>=5;
    if(!turn && B[wz]>>add&1 && (B[wz]-=(1<<add)));
    if(turn && !(B[wz]>>add&1) && (B[wz]+=(1<<add)));
}

inline bool find(int wz) {
    return B[wz>>5]>>(wz&31)&1;
}

inline bool sushu(int a) {
	if(a==43 || a==47 || a==53 || a==59 || a==61 || a==67 || a==71) {
		return 1;
	}
	if(a==41 || a==37 || a==31 || a==29 || a==23 || a==19 || a==17 || a==13 || a==11 || a==7 || a==5 || a==3 || a==2) {
		return 1;
	}
	return 0;
} 

int dp[10000010]; // double prime
int ans[10000010];
int k=0;
inline void work() {
	const int n=100000000;
	change(1,1);
	for(register int i=2; i<=n; ++i) {
		if(!find(i)) {
			dp[++k]=i;
		}
		for(register int j=1; j<=k && i*dp[j]<=n; ++j) {
			change(dp[j]*i,1);
			if(!(i%dp[j])) {
				break;
			}
		}
	}
	int k1=k;
	k=0;
	for(register int i=1; i<=k1; ++i) {
		int sum=0,t=dp[i];
		while(t) {
			sum+=t%10;
			t/=10;
		}
		if(sushu(sum)) {
			ans[++k]=dp[i];
		}
	}
}

int main() {
	work();
	register int t,l,r;
	cin>>t;
	for(; t; --t) {
		cin>>l>>r;
		cout<<upper_bound(ans+1,ans+k+1,r)-lower_bound(ans+1,ans+k+1,l)<<endl;
	}
	return 0;
}