P7588 双重素数（2021 CoE-II A）题解
王熙文
·
·
题解
题目传送门
前置知识：欧拉筛
思路：
$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)`。
这是我的代码：
```cpp
#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](https://www.luogu.com.cn/blog/wangxiwen/you-hua-bool-shu-zu-kong-jian)。下面是我的用这种方式做的代码：
```cpp
#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;
}
```