题目名称是吸引你点进来的
实际上该题还是很水的
题目描述
区间质数个数
输入输出格式
输入格式：
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间
输出格式：
对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing the line
输入输出样例
输入样例#1：
2 5 1 3 2 6
输出样例#1：
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
其实就是想写写莫队练练（你信么），然而这个优雅的暴力还是超时一个点：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1000010;
int answer[N],pos[N],become_answer;
bool vis[N];
int block,js,n,m;
struct node{
int l,r,num;
}E[N];
inline int read()
{
int x=0;int f=1;char c=getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();
return x*f;
}
inline void important()
{
for(int i=2;i<=sqrt(N+1);i++)
if(!vis[i])
for(int j=i*2;j<=N;j+=i)
vis[j]=1;
vis[0]=vis[1]=1;
}
inline bool cmp(node a,node b)
{
if(pos[a.l]==pos[b.l])
return a.r<b.r;
else
return a.l<b.l;
}
inline void add(int x)
{
if(!vis[x])
become_answer++;
}
inline void dale(int x)
{
if(!vis[x])
become_answer--;
}
inline void MD()
{
int l=1,r=1;
for(int i=1;i<=js;i++)
{ int ll=E[i].l,rr=E[i].r;
for(;l<E[i].l;l++)dale(l);
for(;l>E[i].l;l--)add(l-1);
for(;r>E[i].r;r--)dale(r);
for(;r<E[i].r;r++)add(r+1);
answer[E[i].num]=become_answer;
}
}
int main()
{
important();
n=read(),m=read();
for(int i=1;i<=n;i++)
{
int l=read(),r=read();
if(l<1||r<1||l>m||r>m)
answer[i]=-1;
else
{
E[++js].l=l;
E[js].r=r;
E[js].num=i;
}
}
block=sqrt(m);
for(int i=1;i<=m;i++)
pos[i]=(i-1)/block+1;
sort(E+1,E+js+1,cmp);
MD();
for(int i=1;i<=n;i++)
if(answer[i]==-1)
printf("Crossing the line\n");
else
printf("%d\n",answer[i]);
return 0;
}
水一波前缀和：
#include <cstdio>
#include<iostream>
#include<algorithm>
const int N=1000005;
using namespace std;
int n,m,l,r,s[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=2;i<=m;i++)s[i]=1;
for(int i=2;i*i<=m;i++)
for(int j=i+i;j<=m;j+=i)
s[j]=0;
for(int i=1;i<=m;i++)
s[i]+=s[i-1];
while(scanf("%d%d",&l,&r)==2)
(l<1||r>m)?printf("Crossing the line\n"):printf("%d\n",s[r]-s[l-1]);
}