## A % B Problem ##
题目背景
题目名称是吸引你点进来的
实际上该题还是很水的
题目描述
区间质数个数
输入格式:
一行两个整数 询问次数 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
这道题其实不难, 线性素数判断 + 前缀和, 前缀和很好理解, 线性素数判断也就是一种标记素数的方法, 把所有质数的倍数标记为 F, 剩下的就是质数啦! 最后用 f[n] 数组求前 n 项的素数个数, 输出 f[r]-f[l] 也就行了.
注意: 如果 l 是素数, 还要在 + 1!!!
- #include<cstdio>
- #include<cstring>
- using namespace std;
- int f[1100000];
- bool b[1100000];
- int pd(int n)
- {
- f[1]=0;b[1]=false;
- for(int i=2;i<=n;i++)
- {
- if(b[i]==true)
- {
- f[i]=f[i-1]+1;
- for(int j=i+i;j<=n;j+=i)b[j]=false;
- }
- else f[i]=f[i-1];
- }
- }
- int main()
- {
- memset(b,true,sizeof(b));
- int n,m;
- scanf("%d%d",&n,&m);
- pd(m);
- for(int i=1;i<=n;i++)
- {
- int l,r;
- scanf("%d%d",&l,&r);
- if(l<=0||r>=m+1)printf("Crossing the line\n");
- else
- {
- if(b[l]==true)printf("%d\n",f[r]-f[l]+1);
- else printf("%d\n",f[r]-f[l]);
- }
- }
- return 0;
- }
[洛谷 P1865]A % B Problem
来源: http://www.bubuko.com/infodetail-3167239.html