网站建设方案对比分析,第一网站ppt模板,网站建设合作流程,良品铺子vi设计手册一#xff0c;题目#xff1a;
Rain Sure同学定义了幸运数字——如果一个正整数n是幸运数字#xff0c;那么当且仅当n和(n1)/2都是素数。
现在给定q次查询#xff1a;
第i次询问给定两个正整数li,ri#xff0c;请你求出在区间[li,ri]中有多少个数字是幸运数字。…一题目
Rain Sure同学定义了幸运数字——如果一个正整数n是幸运数字那么当且仅当n和(n1)/2都是素数。
现在给定q次查询
第i次询问给定两个正整数li,ri请你求出在区间[li,ri]中有多少个数字是幸运数字。
输入格式
第一行一个正整数q。
后面q行每行两个正整数li,ri
1≤q≤105
1≤li≤ri≤105
输出格式
对于每次询问输出答案每个答案单独占据一行。
测试样例一
1
3 72测试样例二
4
13 13
7 11
7 11
2017 20171
0
0
1测试样例三
6
1 53
13 91
37 55
19 51
73 91
13 494
4
1
1
1
2 二思路
将1-1e5所有幸运数预处理出来利用前缀和来维护每个区间的幸运数数量。
三代码
#include iostream
#includealgorithm
#includecmath
#includecstring
#includeset
#includestack
#includequeue
#includemap
using namespace std;const int N1e510,M1e97;typedef long long ll;
typedef pairint,int pii;bool isprime(int x){for(int i2;ix/i;i){if(x%i0) return false;}return true;
}int st[N];
int pre[N];void Solved() {int q;cinq;for(int i2;i1e5;i){if(isprime(i)) st[i]1;}//预处理for(int i2;i1e5;i){if(st[(i1)/2]1st[i]1){pre[i]1;}}//前缀和for(int i2;i1e5;i){pre[i]pre[i-1];}while(q--){int l,r;cinlr;//查询区间coutpre[r]-pre[l-1]endl;}
}int main()
{int t;//cint;t1;while(t--) {Solved();}return 0;
}
