P1865 A % B Problem

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1865



题目背景
题目名称是吸引你点进来的

实际上该题还是很水的

题目描述
区间质数个数

输入输出格式
输入格式：
一行两个整数 询问次数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

倚窗倾听风吹雨

1. #include<iostream>
   
2. #define FOR(i,a,b) for(int i=a;i<=b;i++)
   
3. #define ROF(i,a,b) for(int i=a;i>=b;i--)
   
4. using namespace std;
   
5. int prime[10000005],f[10000005],n,m,a,b,t,tot;
   
6. bool num[10000005];
   
7. void eural(int x)
   
8. {
   
9.     f[1]=0;
   
10.     FOR(i,2,x)
    
11.     {
    
12.         if(!num[i])
    
13.         {
    
14.             prime[++tot]=i;
    
15.             f[i]=f[i-1]+1;
    
16.         }
    
17.         else
    
18.             f[i]=f[i-1];
    
19.         FOR(j,1,tot)
    
20.         {
    
21.             if(i*prime[j]>x)
    
22.                 break;
    
23.             num[i*prime[j]]=1;
    
24.             if(i%prime[j]==0)
    
25.                 break;
    
26.         }
    
27.     }
    
28. }
    
29. int main()
    
30. {
    
31.     cin>>n>>m;
    
32.     eural(m);
    
33.     while(n--)
    
34.     {
    
35.         cin>>a>>b;
    
36.         if(a<1 || b>m)
    
37.         {
    
38.             cout<<"Crossing the line"<<endl;
    
39.             continue;
    
40.         }
    
41.         else
    
42.         {
    
43.             t=f[b]-f[a-1];
    
44.             cout<<t<<endl;
    
45.         }
    
46.     }
    
47.     return 0;
    
48. }
    

复制代码