首页 > 其他分享 >P7200 [COCI2019-2020#1] Lutrija

P7200 [COCI2019-2020#1] Lutrija

时间:2023-09-22 12:44:29浏览次数:32  
标签:COCI2019 质数 构造 2020 P7200 Lutrija 复杂度

发现相邻的奇数只能恰好差 \(2\)(偶质数只有 \(2\))。

而大于 \(3\) 的三个连续奇数至多有两个是质数,因为有一个能被 \(3\) 整除。对于 3 5 7 这三个数,我们可以构造成 3 5 2 7 以归入下面的构造方法。

所以相邻的奇数最多只有两个。

但我们可以放偶质数 \(2\)。显然,放多个 \(2\) 肯定不优。

于是我们就有 A A-2/A+2 2 B-2/B+2 B 这样的构造形式,根据情况可以省略部分。

这样就能过了,本着精益求精的精神我们继续探究。

拿 \(A\) 来讲,要存在合法的情况必须满足 \(A\) 是孪生质数中的一个。

假设 \(A\) 和 \(A-2\) 是质数,我们显然不需要构造一个 \(A-2\) 项因为 \(A\) 和 \(2\) 的差就是 \(A-2\)。

所以就可以少判断 \(A-2\) 这一项啦。

时间复杂度即为判断质数的复杂度。值得注意的是,除了 3 5 7 这种特殊情况,其余构造出来的解都是最短的。

标签:COCI2019,质数,构造,2020,P7200,Lutrija,复杂度
From: https://www.cnblogs.com/landsol/p/17722058.html

相关文章

  • 已解决 File “F:\File_Anaconda\2020CV\yolov5-master\20200701.py“, line 5 Sy
    已解决File“F:\File_Anaconda\2020CV\yolov5-master\20200701.py”,line5SyntaxError:Non-UTF-8codestartingwith‘\xc0’infileF:\File_Anaconda\2020CV\yolov5-master\20200701.pyonline5,butnoencodingdeclared;seehttp://python.org/dev/peps/pe......
  • Buuctf——[网鼎杯 2020 青龙组]AreUSerialz
    这是一道序列化的题目<?phpinclude("flag.php");highlight_file(__FILE__);classFileHandler{protected$op;protected$filename;protected$content;function__construct(){$op="1";$filename="/......
  • 2020ICPC区域赛南京站
    2020ICPC区域赛南京站KCo-primePermutation解题思路:首先,根据样例2不难发现,\(k\)的下界为\(1\),因为1和排列中的任何数都会互质。其次,我们考虑下上界大概是多少,也就是\(k=n\)是否一定合法。假设,我们有一个初识排列\(p_i=i\).此时我们有\(1\)个元素和他的下标互质。根据......
  • 揭秘ES2020令人兴奋的语言特性
    大家好!我是星辰编程理财。今天我分享一篇关于ES2020(ES11)的文章,它将介绍ES2020的语言特性和功能,包括可选链操作符、空值合并操作符、Promise.allSettled()、import.meta等等。通过故事形式以及详细的阐述和示例,带领大家一起探索这些特性的用处,作为刚入门的新手,它能让你能够在前端开......
  • AS-2020?TSN CoreSolution直接拿下!
    协议简介  IEEE802.1AS是一个网络时间同步协议,它是IEEE802.1工作组的一部分,主要用于支持时间敏感的应用在桥接网络中的时间同步。802.1AS协议专门为了满足TSN网络中设备的时间同步需求而设计。TSN是一种网络技术,它可以提供精确的时间同步和低延迟,从而保障音视频、传感器、......
  • Autocad Electrical 2020中文电气版64位下载 各个版本下载
    AutoCADElectrical2020官方版功能进行了全面升级和优化,比如增加了新的深色主题,可以让你的注意力更集中;增加了新的“经设计展开”图标;用户界面现在经过了优化,现在可以支持高分辨率显示器;而在已发布的PDF文档中,交互参考中现在提供了超链接等等,能够更好的为用户提供服务。软件地址:看......
  • Sketchup 2015、2016、2017、2018、2019、2020、2021、2022、2023(草图大师)下载
    SketchUp是一套直接面向设计方案创作过程的设计工具,其创作过程不仅能够充分表达设计师的思想而且完全满足与客户即时交流的需要,它使得设计师可以直接在电脑上进行十分直观的构思,是三维建筑设计方案创作的优秀工具。草图大师也就是SketchUp,是一个建筑景观专业的3D建模软件,由于运行......
  • 2020-8-19-想在一台电脑好好学知识又想···打游戏
    layout:posttitle:想在一台电脑好好学知识又想···打游戏.categories:pythontag:python开始请注意,这个程序不追求性能,只是追求完成目标这个问题的初衷已经很详细的描述在标题上了所以怎么办呢?我手上有两个屏幕,一边拿来玩游戏,一边拿来看网络教学视频不美哉?问题是游......
  • 2020-2-3-coding新建迭代
    layout:posttitle:coding新建迭代categories:coding-posttag:codingapicoding新建迭代接口URLhttps://<team-name>.coding.net/api/project/<project-id>/iterations请注意,是项目id非名称,id可通过获取项目列表查询请求方式POST请求Content-Typeapplication/json......
  • 2020-2-3-coding迭代查询
    layout:posttitle:coding迭代查询categories:coding-posttag:codingapicoding迭代查询接口URLhttps://<team-name>.coding.net/api/project/<project-id>/iterations?page=1&pageSize=20&keywords=&sortBy=CODE%3ADESC请求方式GET请求header参数:cookie......