华师一附中OI组

标题: P1865 A % B Problem [打印本页]
作者: 倚窗倾听风吹雨    时间: 2018-9-23 14:01
标题: 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
作者: 倚窗倾听风吹雨    时间: 2018-9-23 14:02
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2