【蓝桥杯冲冲冲】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] 开源流程引擎哪个好,如何选型?
开源流程引擎是指一种自动化的工作流解决方案,它可以帮助你管理和协调你的业务流程和决策。但是,在开源世界里,有许多不同的流程引擎可以选择。因此,如何选择适合你的开源流程引擎,是一个具有挑战性和价值的话题。 文章…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...