洛谷P1865题解

发表于 | 评论数： | 阅读次数：

P1865 A%B Problem

题目描述

区间质数个数。

输入输出格式

输入格式

一行两个整数 询问次数$n$，范围$m$。
接下来$n$行，每行两个整数 $l,r $表示区间。

输出格式

对于每次询问输出个数$ t$。
如$l$或$r∉[1,m]$输出$ Crossing the line$。

INPUT & OUTPUT’s examples

Input’s eg #1

1
2
3
2 5
1 3
2 6

Output’s eg #1

1
2
2
Crossing the line

分析

我们对于区间$(1,n]$进行一遍埃式筛，区间和直接用前缀和处理。

最后，f[r]-f[l-1]即是答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/* Omnipotent__Header */
#include<bits/stdc++.h>
/* namespace of std */
using namespace std;
/* namespaces */
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* defintions */
int f[1000001];
bool vis[1000001];
/* functions */
void Eratostnies(int n){
    f[1]=0;
    vis[1]=true;
    for(int i=2;i<=n;i++){
        if(vis[i]==false) {
            f[i]=f[i-1]+1;
            for(int j=i+i;j<=n;j=j+i){
                vis[j]=true;
            }
        }
        else f[i]=f[i-1];
    }
}
int main(){
    int n,m;
    scanf("%d%d",&m,&n);
    Eratostnies(n);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        if(l<1 || r>n) cout<<"Crossing the line"<<endl;
        else{
            int y=f[r]-f[l-1];
            cout<<y<<endl;
        }
    }
    return 0;
}