题目描述
题目背景
题目名称是吸引你点进来的【你怎么知道的】
实际上该题还是很水的【有种不祥的预感。。】
题目描述
区间质数个数
输入输出格式
输入格式：
一行两个整数 询问次数n，范围m接下来n行，每行两个整数 l,r 表示区间。
输出格式：
对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing the line
输入输出样例
输入样例：
2 5
1 3
2 6
输出样例：
2
Crossing the line
说明
数据范围和约定
对于20%的数据 1<=n<=10 1<=m<=10
对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000【吓死我了。。】
题目分析
这题是一道相对基础的数论题，就是求区间素数。然而普通的暴力枚举是绝对会超时的，在这里就不给出暴搜代码了(写了好久的优化，连暴搜都不会写了…)，那么，如何改进算法呢？这里给出两个优化：线筛素数和前缀和(如果神牛有更好的意见请无视其方法并在下方评论写出最优方案，本蒟蒻需要你们的帮助，飞出垃圾堆…)
百科·线性筛素数
用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。(本方法由欧拉大佬荣誉出品~)
前缀和
先分解为一个小问题：
给定n个数ai以及m个询问。
每次询问一段区间的和。
复杂度O(n+m)。
我们可以这样想：
令s[i]=s[i−1]+a[i]" role="presentation" style="position: relative;">s[i]=s[i−1]+a[i]s[i]=s[i−1]+a[i]。
于是有s[i]=a[1]+a[2]+…+a[i]" role="presentation" style="position: relative;">s[i]=a[1]+a[2]+…+a[i]s[i]=a[1]+a[2]+…+a[i]。
求∑a[i]|(i=l,l+1...,r)" role="presentation" style="position: relative;">∑a[i]|(i=l,l+1...,r)∑a[i]|(i=l,l+1...,r)相当于是s[r]−s[l−1]" role="presentation" style="position: relative;">s[r]−s[l−1]s[r]−s[l−1].
我们可以先用欧拉大佬的线筛素数求出区间1~R的素数个数再减去1~L的素数个数即为答案。嗯….于是…就有了代码。
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,cont[1000005];
bool isPrime[1000005];
int main()
{
scanf("%d%d",&n,&m);
memset(isPrime,0,sizeof(isPrime));
isPrime[1]=true;
for(int i=2;i<=sqrt(m);i++)
{
if(isPrime[i]==0)
{
for(int j=2*i;j<=m;j+=i)
isPrime[j]=true;
cont[i]=cont[i-1]+1;
}
else cont[i]=cont[i-1];
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&l,&r);
if(l<1||r>m)
printf("Crossing the line\n");
else
printf("%d\n",cont[r]-cont[l-1]);
}
}