洛谷P1865 A % B Problem

朱雀 2022-05-26 12:05 133阅读 0赞

## 题目背景 ##

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

实际上该题还是很水的

## 题目描述 ##

区间质数个数

## 输入输出格式 ##

输入格式：

一行两个整数 询问次数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

素数筛法+前缀和

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    #define Maxn 10000009
    int res;
    bool is_prime[Maxn];
    int sum[Maxn];//前缀和，记录前i个素数的个数
    void get_prime(int n)
    {
    	res = 0;
    	memset(is_prime, 0, sizeof(is_prime));
    	is_prime[0] = is_prime[1] = 1;
    	for (int i = 2; i <= n; i++)
    	{
    		if (!is_prime[i])
    		{
    			//prime[res++] = i;
    			for (int j = 2; j*i <= n; j++)is_prime[j*i] = 1;
    			sum[i] = sum[i - 1] + 1;
    		}
    		else
    			sum[i] = sum[i - 1];
    	}
    }
    int n, m;
    int l, r;
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> n >> m;
    	get_prime(m);
    	while (n--)
    	{
    		cin >> l >> r;
    		if (l <= m&&r <= m&&l >= 1 && r >= 1)
    		{
    			cout << sum[r]-sum[l-1] << endl;
    		}
    		else{
    			cout << "Crossing the line" << endl;
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷---P1102 A-B 数对---双指针算法

> 题目链接： > [P1102 A-B 数对][P1102 A-B] > 题目描述： > ![在这里插入图片描述][096c83e558174a7da38d661

小咪咪/ 2024年03月26日 12:41/ 0 赞/ 2 阅读

相关 P1001: A + B Problem II

P1001: A + B Problem II 题目描述 I have a very simple problem for you. Given two intege

╰+哭是因爲堅強的太久メ/ 2022年12月04日 01:21/ 0 赞/ 124 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 244 阅读

相关洛谷P1164 小A点菜

题目背景 uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。 uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。题

曾经终败给现在/ 2022年05月28日 07:10/ 0 赞/ 121 阅读

相关洛谷P1865 A % B Problem

题目背景题目名称是吸引你点进来的实际上该题还是很水的题目描述区间质数个数输入输出格式输入格式：一行两个整数询问次数n，范围m

朱雀/ 2022年05月26日 12:05/ 0 赞/ 134 阅读

相关洛谷P1604 B进制星球

题目背景进制题目，而且还是个计算器~~ 题目描述话说有一天，小Z乘坐宇宙飞船，飞到一个美丽的星球。因为历史的原因，科技在这个美丽的星球上并不很发达，星球上人们

柔情只为你懂/ 2022年05月26日 08:18/ 0 赞/ 134 阅读

相关洛谷P1303 A*B Problem

题目描述求两数的积。输入输出格式输入格式：两行，两个数。输出格式：积输入输出样例输入样例\1：复制 1

梦里梦外;/ 2022年05月26日 05:44/ 0 赞/ 128 阅读

相关洛谷 P1601 A+B Problem（高精）

题目背景无题目描述高精度加法,x相当于a+b problem，\[b\]\[color=red\]不用考虑负数\[/color\]\[/b\] 输入输出

秒速五厘米/ 2022年05月26日 03:37/ 0 赞/ 106 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 229 阅读

相关洛谷P2709 小B的询问

莫队模版本来想能不学莫队就不学，但是这次比赛被莫队卡得好惨，于是学了一发。。先切道模板题。。最普通的莫队就是把序列分块，然后按照询问所在的块来排序，减少指针的移

矫情吗；*/ 2022年01月07日 05:19/ 0 赞/ 168 阅读