【蓝桥杯冲冲冲】Prime Gift
【蓝桥杯冲冲冲】Prime Gift
蓝桥杯备赛 | 洛谷做题打卡day31
文章目录
- 蓝桥杯备赛 | 洛谷做题打卡day31
- Prime Gift
- 题面翻译
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 样例 #2
- 样例输入 #2
- 样例输出 #2
- 提示
- 题解代码
- 我的一些话
-
Prime Gift
题面翻译
给你 n n n 个互不相同的素数 p 1 , p 2 , ⋯ , p n p_1,p_2,\cdots,p_n p1,p2,⋯,pn,它们组成一个集合 P P P。
请你求出第 k k k 小的正整数,满足:
- 该数字的所有素因子 ∈ P \in P ∈P
1 ≤ n ≤ 16 , 2 ≤ p i ≤ 100 , 1\le n\le 16,2\le p_i\le 100, 1≤n≤16,2≤pi≤100, 保证答案不超过 1 0 18 10^{18} 1018。
题目描述
Opposite to Grisha’s nice behavior, Oleg, though he has an entire year at his disposal, didn’t manage to learn how to solve number theory problems in the past year. That’s why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of $ n $ distinct prime numbers alongside with a simple task: Oleg is to find the $ k $ -th smallest integer, such that all its prime divisors are in this set.
输入格式
The first line contains a single integer $ n $ ( $ 1<=n<=16 $ ).
The next line lists $ n $ distinct prime numbers $ p_{1},p_{2},…,p_{n} $ ( $ 2<=p_{i}<=100 $ ) in ascending order.
The last line gives a single integer $ k $ ( $ 1<=k $ ). It is guaranteed that the $ k $ -th smallest integer such that all its prime divisors are in this set does not exceed $ 10^{18} $ .
输出格式
Print a single line featuring the $ k $ -th smallest integer. It’s guaranteed that the answer doesn’t exceed $ 10^{18} $ .
样例 #1
样例输入 #1
3 2 3 5 7
样例输出 #1
8
样例 #2
样例输入 #2
5 3 7 11 13 31 17
样例输出 #2
93
提示
The list of numbers with all prime divisors inside $ {2,3,5} $ begins as follows:
$ (1,2,3,4,5,6,8,…) $
The seventh number in this list ( $ 1 $ -indexed) is eight.
题解代码
学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是题解代码 ~
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define REP(a,b,c) for(int a=b;a<=c;a++)
int n,a[110],k;
LL A[5000010],B[5000010];
int lenA=0,lenB=0;
inline void dfs1(int x,LL s) {A[++lenA]=s;if (x>n) return ;for(LL i=1;;i*=a[x]) {if (1e18/i<s) break;dfs1(x+2,s*i);}
}
inline void dfs2(int x,LL s) {B[++lenB]=s;if (x>n) return ;for(LL i=1;;i*=a[x]) {if (1e18/i<s) break;dfs2(x+2,s*i);}
}
inline LL check(LL mid) {LL ans=0; int j=lenB;REP(i,1,lenA) {while (j>0&&B[j]>mid/A[i]) j--;ans+=1ll*j;}return ans;
}
int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin>>n; REP(i,1,n) cin>>a[i]; cin>>k;sort(a+1,a+n+1);dfs1(1,1); dfs2(2,1);LL l=0,r=1e18;sort(A+1,A+lenA+1);sort(B+1,B+lenB+1);lenA=unique(A+1,A+lenA+1)-A-1;lenB=unique(B+1,B+lenB+1)-B-1;while (l<r) {LL mid=(l+r)>>1;if (check(mid)>=k) r=mid;else l=mid+1;}cout<<r<<endl;return 0;
}//完结撒花! の_^
我的一些话
-
今天学习动态规划,dp属于比较难的部分,这题利用记忆化搜索即可快速解决,需要多动脑,多思考思路还是很好掌握的,虽然一次性AC有一定难度,需要通盘的考虑和理解,以及扎实的数据结构基础才能独立写出AC代码。但无论难易,大家都要持续做题,保持题感喔!一起坚持(o´ω`o)
-
如果有非计算机专业的uu自学的话,关于数据结构的网课推荐看b站上青岛大学王卓老师的课,讲的很细致,有不懂都可以私信我喔
-
总结来说思路很重要,多想想,多在草稿纸上画画,用测试数据多调试,debug后成功编译并运行出正确结果真的会感到很幸福!
-
关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识,之前的博文我都有写,欢迎大家关注我,翻阅自取哦~
-
不管什么都要坚持吧,三天打鱼两天晒网无法形成肌肉记忆和做题思维,该思考的时候一定不要懈怠,今天就说这么多啦,欢迎评论留言,一起成长:)
相关文章:

【蓝桥杯冲冲冲】Prime Gift
【蓝桥杯冲冲冲】Prime Gift 蓝桥杯备赛 | 洛谷做题打卡day31 文章目录 蓝桥杯备赛 | 洛谷做题打卡day31Prime Gift题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示题解代码我的一些话 Prime Gift 题面翻译 给你 n n n 个…...

【PyQt】06-.ui文件转.py文件
文章目录 前言方法一、基本脚本查看自己的uic安装目录 方法二、添加到扩展工具里面(失败了)方法二的成功步骤总结 前言 方法一、基本脚本 将Qt Designer(一种图形用户界面设计工具)生成的.ui文件转换为Python代码的脚本。 pytho…...
λ-矩阵知识点
原文:链接 λ-矩阵 若矩阵 A \mathbf{A} A 的元素为关于 λ λ λ 的多项式,则称 A \mathbf{A} A 为 λ λ λ-矩阵 (表示为 A ( λ ) \mathbf{A}(λ) A(λ)). λ λ λ-矩阵也存在秩、逆、初等变换、相抵的概念, 但是有一些不同. 定义. λ λ λ-矩阵的秩是…...

cocos creator 3.x 预制体无法显示
双击预制体,进入详情页,没有显示资源 Bomb 是个预制体,但是当我双击进来什么都没有了,无法对预制体进行可视化编辑 目前我只试出来一个解决方法: 把预制体拖进Canvas文件中,这样就能展示到屏幕上ÿ…...

Tomcat之虚拟主机
1.创建存放网页的目录 mkdir -p /web/{a,b} 2.添加jsp文件 vi /web/a/index.jsp <% page language"java" import"java.util.*" pageEncoding"UTF-8"%> <html> <head><title>JSP a page</title> </head> …...

前后端数据校验
前端校验内容 前端开发中的必要校验,可以保证用户输入的数据的准确性、合法性和安全性。同时,这些校验也有助于提供良好的用户体验和防止不必要的错误提交到后端。 1、必填字段校验: 对于必填的字段,需确保用户输入了有效的数据…...
Python把png图片转成jpg图片
在Python中,您可以使用PIL(Python Imaging Library,也被称为Pillow)库来将PNG图片转换为JPG格式。以下是一个简单的示例: 首先,确保你已经安装了Pillow库。如果没有安装,可以使用pip来安装&…...

STM32搭建开发环境
常用开发工具简介 集成开发环境 MDK:全名RealViewMDK,是Keil公司(已被ARM收购的)一款集成开发环境,界面美观,简单易用,是STM32最常用的集成开发环境EWARM:IAR公司的一款集成开发环…...

C#入门详解_01_课程简介、C#语言简介、开发环境和学习资料的准备
文章目录 1. 课程简介2. C#语言简介3.开发环境与学习资料 1. 课程简介 开设本课程的目的 传播C#开发的知识,让更多的人有机会接触到软件开发行业引导有兴趣或者想转行的朋友进入软件开发行业 课程内容 完整讲述C#语言在实际软件开发中的应用采用知识讲述加实例程序…...
C++服务器端开发(2):确定服务器框架
选择C服务器框架时,可以考虑: 并发性能:C的强项之一是其并发性能。选择一个具有高并发处理能力的服务器框架,可以更好地满足大量并发请求的需求。例如,libevent、Boost.Asio和CppServer都是具有良好并发性能的C服务器框…...
CGAL::2D Arrangements-5
5.Arrangement无界曲线 前几章中构建和操作的所有Arrangement都只由线段引起,线段尤其是有界曲线。这样的Arrangement总是具有一个包含所有其他Arrangement特征的unbounded face。在本节中,我们将解释如何构造无界曲线的Arrangement。为了简化说明&…...

登录+JS逆向进阶【过咪咕登录】(附带源码)
JS渗透之咪咕登录 每篇前言:咪咕登录参数对比 captcha参数enpassword参数搜索enpassword参数搜索J_RsaPsd参数setPublic函数encrypt加密函数运行时可能会遇到的问题此部分改写的最终形态JS代码:运行结果python编写脚本运行此JS代码:运行结果&…...

CTF秀 ctfshow WEB入门 web1-10 wp精讲
目录 web1_查看源码 web3_抓包 web4-9_目录文件 web10_cookie web1_查看源码 ctrlu 查看源码 web3_抓包 查看源码,无果 抓包,找到flag web4-9_目录文件 GitHub - maurosoria/dirsearch: Web path scanner 下载dirsearch工具扫一下就都出来了 web4-…...

centos安装inpanel
前置条件 安装python yum -y install python 安装 cd /usr/local git clone https://gitee.com/WangZhe168_admin/inpanel.git cd inpanel python install.py 安装过程需要设置账户 密码 端口号 我设置的是admin:admin 10050 使用 打开浏览器,输入 http://192.168.168.…...
聊聊PowerJob Worker的ServerAddress
序 本文主要研究一下PowerJob Worker的ServerAddress PowerJobAutoConfiguration tech/powerjob/worker/autoconfigure/PowerJobAutoConfiguration.java BeanConditionalOnMissingBeanpublic PowerJobSpringWorker initPowerJob(PowerJobProperties properties) {PowerJobPr…...
师傅带练|大数据人工智能在线实习项目特色
大数据人工智能八大在线实习项目: 某实习网站招聘信息采集与分析 股票价格形态聚类与收益分析 某平台网络入侵用户自动识别 某平台广东省区采购数据分析 产品订单的数据分析与需求预测 基于注意力机制的评论者满意度分析 基于锅炉工况实现…...

ant-design-vue表格嵌套子表格,实现子表格有数据才显示左侧加号图标
ant-design-vue表格嵌套子表格,实现子表格有数据才显示左侧加号图标 通过使用插槽的方式,以下为全部项目的代码,关键的代码就两块,看注释 <template><a-card><a-form class"kit_form" ref"formRef…...

浅谈垃圾回收、内存泄漏与闭包
什么是垃圾? 在js中,垃圾通常指的是不再被程序使用的内存或对象。也就是说,垃圾是指程序中分配的内存空间或对象,但不再被程序使用或无法被访问到的内容 function createIncrease() {const doms new Array(100000).fill(0).map((…...

2 月 7 日算法练习- 数据结构-树状数组
树状数组 lowbit 在学习树状数组之前,我们需要了解lowbit操作,这是一种位运算操作,用于计算出数字的二进制表达中的最低位的1以及后面所有的0。 写法很简单: int lowbit(int x){return x &am…...
[AIGC] 开源流程引擎哪个好,如何选型?
开源流程引擎是指一种自动化的工作流解决方案,它可以帮助你管理和协调你的业务流程和决策。但是,在开源世界里,有许多不同的流程引擎可以选择。因此,如何选择适合你的开源流程引擎,是一个具有挑战性和价值的话题。 文章…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...

企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...

从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...