洛谷 P1865 A % B Problem[筛素数/前缀和思想/区间质数个数]
2024-09-06 20:46:55
题目描述
区间质数个数
输入输出格式
输入格式：
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间
输出格式：
对于每次询问输出个数 t，如l或r∉[1,m]输出 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
【分析】:不用前缀和就TLE阿QAQ
【代码】：
#include <bits/stdc++.h> using namespace std;
int const MAX = ;
int const INF = 0x3fffffff;
int n, m;
int a[];
int isP(int n)
{
if(n == ) return ;
for(int i=; i<=sqrt(n); i++){
if(n % i == ){
return ;
}
}
return ;
} int main()
{
cin >> n >> m;
a[] = ;
int l, r, ans = ; for(int i=; i<=m; i++){
if( i%!= || i==){
a[i] = a[i-] + isP(i);
}
else{
a[i] = a[i-];
}
}
//a[i]=isP(i)+a[i-1]是a[i]=a[i]前所有素数的个数，如果i是素数 a[i]要加一，否则不加（判素数的函数回的是1或0）
while(n--){
ans = ;
cin >> l >> r;
if(l<||r>m){
printf("Crossing the line\n");
}
else{
printf("%d\n",a[r] - a[l-]);
} }
}
暴力筛
#include <bits/stdc++.h> using namespace std;
int const MAX = ;
int const INF = 0x3fffffff;
int n, m, l, r;
int a[MAX];
int sum[MAX];
int main()
{
cin >> n >> m;
a[] = ; for(int i=; i<=sqrt(m); i++){
if(!a[i]){
for(int j=i+i; j<=m; j+=i){
a[j] = ;
}
}
} for(int i=; i<=m; i++){
sum[i] = sum[i-] + (a[i]^);//异或 ：a[i] = 0 ——> +1 / a[i] = ——> +0
} for(int i=; i<=n; i++){
cin >> l >> r;
if(l< || r>m) puts("Crossing the line");
else{
printf("%d\n",sum[r]-sum[l-]);
}
}
}
埃筛
最新文章
- sass基础编写流程
- Codeforces Round #377 (Div. 2) D. Exams(二分答案)
- Azure ARM (1) UI初探
- 移动端-js触摸事件
- 使用Javascript来编写贪食蛇（零基础）
- 2016年10月16日--ArrayList集合、特殊集合
- Jenkins快速上手
- 面向侧面的程序设计AOP-------《一》概述
- 【windows核心编程】一个API拦截的例子
- JavaScript 客户端JavaScript之 脚本化文档
- JSP SMARTUPLOAD组件:上传文件时同时获取表单参数
- lucene3.6笔记添加搜索功能
- easyui+ztree 后台管理系统模板
- c# datetime与 timeStamp（unix时间戳） 互相转换
- [转]Thunderbird 使用 Exchange 邮箱
- ***报错Class 'Redis' not found in（原创）
- React++ node.js ++SQL Sever ++MySQL++ python ++ php ++ java ++ c++ c#++ java ++ android ++ ios ++Linux+
- iptables防火墙配置
- 001.Heartbeat简介
- 洛谷P1941 飞扬的小鸟 [noip2014] 背包