当前位置: 首页 > news >正文

洛谷题解 | AT_abc321_c Primes on Interval

目录

    • 题目翻译
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 样例 #2
      • 样例输入 #2
      • 样例输出 #2
    • 样例 #3
      • 样例输入 #3
      • 样例输出 #3
    • 题目简化
    • 题目思路
    • AC代码

题目翻译

【题目描述】
你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数,其含义就是除了数字一和本身之外不能被其他任何的数字除尽.

现在给定一个正整数序列 a , a + 1 , ⋯ , b a,a+1,\cdots,b a,a+1,,b ( a ≤ b ) (a \le b) (ab), 请找出一个最小值 l l l, 使其满足对于任意一个长度为 l l l 的子串, 都包含 k k k 个质数.

找到并输出符合要求的最小值 l l l, 如果不存在符合要求的长度 l l l, 则输出 − 1 -1 1.

【输入格式】

输入一行, 包含三个用空格隔开的整数 a , b , k a,b,k a,b,k ( 1 ≤ a , b , k ≤ 1 0 6 ; a ≤ b 1 \le a,b,k \le 10^{6}; a \le b 1a,b,k106;ab)

【输出格式】
输出一行, 为符合要求的最小值 l l l, 若不存在, 输出 − 1 -1 1.

题目描述

You’ve decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors.

Consider positive integers $ a $ , $ a+1 $ , $ … $ , $ b $ $ (a<=b) $ . You want to find the minimum integer $ l $ $ (1<=l<=b-a+1) $ such that for any integer $ x $ $ (a<=x<=b-l+1) $ among $ l $ integers $ x $ , $ x+1 $ , $ … $ , $ x+l-1 $ there are at least $ k $ prime numbers.

Find and print the required minimum $ l $ . If no value $ l $ meets the described limitations, print -1.

输入格式

A single line contains three space-separated integers $ a,b,k $ ( $ 1<=a,b,k<=10^{6}; a<=b $ ).

输出格式

In a single line print a single integer — the required minimum $ l $ . If there’s no solution, print -1.

样例 #1

样例输入 #1

2 4 2

样例输出 #1

3

样例 #2

样例输入 #2

6 13 1

样例输出 #2

4

样例 #3

样例输入 #3

1 4 3

样例输出 #3

-1

题目简化

求一个区间内,任意长度为 l l l 的子串中都包含 k k k 个质数的最小 l l l

题目思路

初始化一个数组存储从 2 2 2 开始的所有素数。初始化后,这个数组中所有值都是 true,表示对应的数是素数。

使用埃拉托斯特尼筛法(Sieve of Eratosthenes)来找出所有小于 M A X MAX MAX 的素数。这个算法的主要思想是,如果一个数不是素数,那么它必定有一个因子小于或等于其平方根。因此,我们只需要检查到每个数的平方根即可。

在主循环中,读取三个输入: a a a, b b b k k k。然后,创建一个队列 q q q 并把 a − 1 a-1 a1 放入队列。

接下来,进行一系列操作来找出在区间 [ a , b ] \text [a, b] [a,b] 中,长度为 k k k 的所有素数子序列。如果存在这样的子序列,那么就更新 r e s res res 的值。

如果 q q q 的头部元素是 a − 1 a-1 a1,那么就输出 -1 \texttt -\texttt 1 -1,否则输出 r e s res res

AC代码

#include <bits/stdc++.h>
using namespace std;
#define li        long long int
#define rep(i,to) for(li i=0;i<((li)(to));++i)
#define pb        push_back
#define sz(v)     ((li)(v).size())
#define bit(n)    (1ll<<(li)(n))
#define all(vec)  (vec).begin(),(vec).end()
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define MP        make_pair
#define F         first
#define S         second#define MAX 1000500
li is_prime[MAX];int main()
{rep(i, MAX)if(2 <= i) is_prime[i] = true;for(li i = 2; i * i < MAX; i++){if(!is_prime[i]) continue;for(li j = i * i; j < MAX; j += i) is_prime[j] = false;}li a, b, k;cin >> a >> b >> k;queue<li> q;li res = -1;q.push(a - 1);for(li pos = a; pos <= b; pos++){if(is_prime[pos]) q.push(pos);while(k < sz(q)) q.pop();if(sz(q) == k) res = max(res, pos - q.front() + 1);}if(q.front() == a - 1) cout << -1 << endl;else cout << res << endl;
} 

创作不易,白嫖不好,各位的支持和认可,就是我创作的最大动力,如果喜欢我的文章,给个关注吧!

冰焰狼 | 文

如果本篇博客有任何错误,请批评指教,不胜感激 !

相关文章:

洛谷题解 | AT_abc321_c Primes on Interval

目录 题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 题目简化题目思路AC代码 题目翻译 【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数&#xff0c;其含义就是除了数…...

Quartus医院病房呼叫系统病床呼叫Verilog,源代码下载

名称&#xff1a;医院病房呼叫系统病床呼叫 软件&#xff1a;Quartus 语言&#xff1a;Verilog 要求&#xff1a; 1、用1~6个开关模拟6个病房的呼叫输入信号,1号优先级最高;1~6优先级依次降低; 2、 用一个数码管显示呼叫信号的号码;没信号呼叫时显示0;有多个信号呼叫时,显…...

ip的标准分类---分类的Ip

分类的 IP 即将 IP 地址划分为若干个固定类&#xff0c;每一类地址都由两个固定长度的字段组成。 其中第一个字段是网络号&#xff08;net-id&#xff09;&#xff0c;它标志主机或路由器所连接的网络。一个网络号在整个因特网内必须是唯一的。 第二个字段是主机号&#xf…...

理解并掌握C#的Channel:从使用案例到源码解读(一)

引言 在C#的并发编程中&#xff0c;Channel是一种非常强大的数据结构&#xff0c;用于在生产者和消费者之间进行通信。本文将首先通过一个实际的使用案例&#xff0c;介绍如何在C#中使用Channel&#xff0c;然后深入到Channel的源码中&#xff0c;解析其内部的实现机制。 使用案…...

如何让git命令仅针对当前目录

背景 我们有时候建的git仓库是这样的&#xff0c;a目录下有b、c、d三个模块&#xff08;文件夹&#xff09;。有时候只想查看b下面的变化&#xff0c;而使用 git status、git diff 的时候会把c和d的变化都列出来&#xff0c;要怎么只查b目录的变化&#xff1f; 操作 要查b目…...

【0223】源码剖析smgr底层设计机制(3)

1. smgr设计机制 PG内核中smgr完整磁盘存储介质的管理是通过下面三部分实现的。 1.1 函数指针结构体 f_smgr 函数指针结构体 f_smgr。 通过该函数指针类型,可完成类似于UNIX系统中的VFD功能,上层只需要调用open()、read()、write()等系统函数,用户不必去关系底层的文件系统…...

Visual Studio 2019 C# winform CefSharp 中播放视频及全屏播放

VS C# winform CefSharp 浏览器控件&#xff0c;默认不支持视频播放&#xff0c;好在有大佬魔改了dll&#xff0c;支持流媒体视频播放。虽然找了很久&#xff0c;好歹还是找到了一个版本100.0.230的dll&#xff08;资源放在文末&#xff09; 首先创建一个项目 第二、引入CefSha…...

天选之子Linux是如何发展起来的?为何对全球IT行业的影响如此之大?

天选之子Linux是如何发展起来的&#xff1f;为何对全球IT行业的影响如此之大&#xff1f; 前言一、UNIX发展史二、Linux发展历史三、开源四、官网五、 企业应用现状六、发行版本 前言 上面这副图是博主历时半小时完成的&#xff0c;给出了Linxu的一些发展背景。球球给位看官老…...

MDK报错:Undefined symbol assert_failed报错解决策略

MDK报错&#xff1a;Undefined symbol assert_failed报错解决策略 &#x1f3af;&#x1fa95;在全网搜索相关MDK编译报错:Error: L6218E: Undefined symbol assert_param (referred from xxx.o). ✨有些问题看似很简单&#xff0c;可能产生的问题是由于不经意的细节原因导致。…...

LLM - Make Causal Mask 构造因果关系掩码

目录 一.引言 二.make_causal_mask 1.完整代码 2.Torch.full 3.torch.view 4.torch.masked_fill_ 5.past_key_values_length 6.Test Main 三.总结 一.引言 Causal Mask 主要用于限定模型的可视范围&#xff0c;防止模型看到未来的数据。在具体应用中&#xff0c;Caus…...

Python函数式编程(一)概念和itertools

Python函数式编程是一种编程范式&#xff0c;它强调使用纯函数来处理数据。函数是程序的基本构建块&#xff0c;并且尽可能避免或最小化可变状态和副作用。在函数式编程中&#xff0c;函数被视为一等公民&#xff0c;可以像值一样传递和存储。 函数式编程概念 编程语言支持通…...

Guava限流器原理浅析

文章目录 基本知识限流器的类图使用示例 原理解析限流整体流程问题驱动1、限流器创建的时候会初始化令牌吗&#xff1f;2、令牌是如何放到桶里的&#xff1f;3、如果要获取的令牌数大于桶里的令牌数会怎么样4、令牌数量的更新会有并发问题吗 总结 实际工作中难免有限流的场景。…...

第四十二章 持久对象和SQL - 用于创建持久类和表的选项

文章目录 第四十二章 持久对象和SQL - 用于创建持久类和表的选项用于创建持久类和表的选项访问数据 第四十二章 持久对象和SQL - 用于创建持久类和表的选项 用于创建持久类和表的选项 要创建持久类及其对应的 SQL 表&#xff0c;可以执行以下任一操作&#xff1a; 使用 IDE …...

集合-ArrayList源码分析(面试)

系列文章目录 1.集合-Collection-CSDN博客​​​​​​ 2.集合-List集合-CSDN博客 3.集合-ArrayList源码分析(面试)_喜欢吃animal milk的博客-CSDN博客 目录 系列文章目录 前言 一 . 什么是ArrayList? 二 . ArrayList集合底层原理 总结 前言 大家好,今天给大家讲一下Arra…...

跨类型文本文件,反序列化与类型转换的思考

文章目录 应用场景序列化 - 对象替换原内容&#xff0c;方便使用编写程序取得结果数组 序列化 - JSON 应用场景 在编写热更新的时候&#xff0c;我发现了一个古早的 ini 文件&#xff0c;记录了许多有用的数据 由于使用的语言年份较新&#xff0c;没有办法较好地对 ini 文件的…...

ubuntu20安装nvidia驱动

1. 查看显卡型号 lspci | grep -i nvidia 我的输出&#xff1a; 01:00.0 VGA compatible controller: NVIDIA Corporation GP104 [GeForce GTX 1080] (rev a1) 01:00.1 Audio device: NVIDIA Corporation GP104 High Definition Audio Controller (rev a1) 07:00.0 VGA comp…...

gma 2 成书计划

随着 gma 2 整体构建完成。下一步计划针对库内所有功能完成一个用户指南&#xff08;非网站&#xff09;。 封皮 主要章节 章节完成度相关链接第 1 章 GMA 概述已完成第 2 章 地理空间数据操作已完成第 3 章 坐标参考系统已完成第 4 章 地理空间制图已完成第 5 章 数学运算模…...

从零手搓一个【消息队列】项目设计、需求分析、模块划分、目录结构

文章目录 一、需求分析1, 项目简介2, BrokerServer 核心概念3, BrokerServer 提供的核心 API4, 交换机类型5, 持久化存储6, 网络通信7, TCP 连接的复用8, 需求分析小结 二、模块划分三、目录结构 提示&#xff1a;是正在努力进步的小菜鸟一只&#xff0c;如有大佬发现文章欠佳之…...

【Spring Cloud】深入探索 Nacos 注册中心的原理,服务的注册与发现,服务分层模型,负载均衡策略,微服务的权重设置,环境隔离

文章目录 前言一、初识 Nacos 注册中心1.1 什么是 Nacos1.2 Nacos 的安装&#xff0c;配置&#xff0c;启动 二、服务的注册与发现三、Nacos 服务分层模型3.1 Nacos 的服务分级存储模型3.2 服务跨集群调用问题3.3 服务集群属性设置3.4 修改负载均衡策略为集群策略 四、根据服务…...

No156.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…...

如何在PIL图像和PyTorch Tensor之间进行相互转换,使用pytorch进行PIL和tensor之间的数据转换

目录 引言PIL简介PyTorch和Torchvision简介PIL转换为TensorTensor转换为PIL实例代码和解释结论参考文献 &#x1f4dd; 引言 在计算机视觉领域&#xff0c;使用图像处理库对图像进行预处理是非常常见的。其中&#xff0c;Python Imaging Library&#xff08;PIL&#xff09;以…...

STM32F4X UCOSIII任务消息队列

STM32F4X UCOSIII任务消息队列 任务消息队列和内核消息队列对比内核消息队列内核消息队列 UCOSIII任务消息队列API任务消息队列发送函数任务消息队列接收函数 UCOSIII任务消息队列例程 之前的章节中讲解过消息队列这个机制&#xff0c;UCOSIII除了有内核消息队列之外&#xff0…...

8个居家兼职,帮助自己在家搞副业

越来越多的人开始追求居家工作的机会&#xff0c;无论是为了获得更多收入以改善生活质量&#xff0c;还是为了更好地平衡工作和家庭的关系&#xff0c;居家兼职已成为一种趋势。而在家中从事副业不仅能够为我们带来额外的收入&#xff0c;更重要的是&#xff0c;它可以让我们在…...

管理与系统思维

技术管理者不仅仅需要做事情&#xff0c;还需要以系统思维的方式推动组织变革&#xff0c;从而帮助团队和个人做到更好。原文: Management and Systems Thinking 图片来源: Dall-E "除非管理者考虑到组织的系统性&#xff0c;否则大多数提高绩效的努力都将注定失败。"…...

电死人的是电流还是电压?

先说答案&#xff0c;是电流。 这个有两个派别&#xff0c;一个是电流派&#xff0c;一个是电压派。 举个例子&#xff0c;拿我们的头发或者指甲之类的高电阻物质去接触高压&#xff0c;你会发现基本没有什么作用&#xff1b;还有就是冬天我们脱毛衣的时候&#xff0c;噼里啪啦…...

mac 编译问题记录

1、mac 编译提示 Unsupported option ‘--no-pie‘ Linux 上用 --no-pie mac 上用 -no-pie 2、mac 找不到 malloc.h 使用 #include <sys/malloc.h> Mac上使用malloc函数报错_mac malloc.h-CSDN博客...

centos 7.9同时安装JDK1.8和openjdk11两个版本

1.使用的原因 在服务器上&#xff0c;有些情况因为有一些系统比较老&#xff0c;所以需要使用JDK8版本&#xff0c;但随着时间的发展&#xff0c;新的软件出来&#xff0c;一般都会使用比较新的JDK版本。所以就出现了我们标题的需求&#xff0c;一个系统内同时安装两个不同的版…...

【JavaEE】HTML

JavaWeb HTML 超文本标记语言 超文本&#xff1a;文本、声音、图片、视频、表格、连接标记&#xff1a;有许许多多的标签组成 vscode开发工具搭建 因为我使用的IDEA是社区版&#xff0c;代码高亮补全缩进都有些问题&#xff0c;使用vscode是最好的选择~ 安装 Visual Stu…...

【数据结构--八大排序】之堆排序

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

c# 中的类

反射 Activator.CreateInstance class Program {static void Main(string[] args){//反射Type t typeof(Student);object o Activator.CreateInstance(t, 1, "FJ");Student stu o as Student;Console.WriteLine(stu.Name);//动态编程dynamic stu2 Activator.Cre…...

wp网站怎么用插件做html网页/济南优化网站关键词

直接把下面代码复制到你要填写的url地址 <?php //定义常量token define(TOKEN,weixin); //检查标签function checkSignature(){//先获取到这三个参数$signature $_GET[signature]; $nonce $_GET[nonce]; $timestamp $_GET[timestamp]; //把这三个参数存到一个数组里面…...

静态网站用什么做最快/广州白云区最新信息

有两个插件可以用 actiBPMActiviti BPMN visualizer 两款插件直接在IDEA插件市场搜索就可以搜到&#xff0c;也可以到官方网站的插件仓库也可以找到。 JetBrains插件市场&#xff1a;https://plugins.jetbrains.com/ 我正在使用的IDEA版本是2020.3&#xff0c;而actiBPM不兼容…...

从零开始网页制作教程/seo辅助工具

情况说明&#xff1a; 联想笔记本电脑&#xff0c;Microsoft Edge主页被恶意篡改为hao123&#xff0c;解决问题的过程中参考了以下方法&#xff1a; winR&#xff0c;输入regedit&#xff0c;修改注册表&#xff1b;进入联想电脑管家检查是否开启浏览器主页保护&#xff1b;进…...

搜索别人的网站是带logo的请问怎么做的/南京响应式网站建设

有 时当 使用 一个 包含 多 个 参 数 的 方 法 时 &#xff0c; 由 于参 数 过 多 会 导 致 可 读 性 严 重 下 降 &#xff0c; 如 &#xff1a; 有 时当 使用 一个 包含 多 个 参 数 的 方 法 时 &#xff0c; 由 于参 数 过 多 会 导 致 可 读 性 严 重 下 降 &#xff0c; …...

给公司创建网站/seo新人怎么发外链

一、前后端分离的优缺点 &#xff1a; 为什么要前后端分离 &#xff1f; 1.pc、app、pad多端适应 传统的后端 模板生成模式只适用于 pc 端&#xff0c;其他的做起来比较麻烦。 2.SPA开发 模式 开始流行 SPA 是指单页面应用程序 3.前后端开发职责不清 django 的 template…...

wordpress 隐藏后台/百度搜索引擎的优缺点

student a am ii ma a tnedutsi am a student代码具体思想1.将句子反转(不管单词拼写顺序)2.将各个单词分别反转为正确顺序源代码&#xff1a;#include#includevoid Reverse(char *left, char *right)//范围反转{char temp;while (left < right){temp *left;*left *right;…...