2021.08.01 P4359 伪光滑数(二叉堆)
2021/8/1 23:08:30
本文主要是介绍2021.08.01 P4359 伪光滑数(二叉堆),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2021.08.01 P4359 伪光滑数(二叉堆)
[P4359 CQOI2016]伪光滑数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意:
若一个大于 11 的整数 MM 的质因数分解有 k 项,其最大的质因子为 a_k,并且满足
\[a_{k}^{k} ≤N,a_k < 128 \],我们就称整数 M 为 N - 伪光滑数。
现在给出 NN,求所有整数中,第 KK 大的 NN - 伪光滑数。
分析:
在k一定时,如果已知p_maxn,则val_maxn=k*p_maxn,每次改去一个质因数p_maxn,压入队列。运用多路归并的思想。
代码如下:
#include<cstdio> #include<algorithm> #include<iostream> #include<queue> using namespace std; #define int long long int n,k; int p[40]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127}; struct node{ int val,maxn,k,last; bool operator <(const node &b)const{ return val<b.val; } }; priority_queue<node>q; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); } while(ch<='9'&&ch>='0'){ s=s*10+ch-'0'; ch=getchar(); } return s*w; } signed main(){ n=read();k=read(); for(int i=1;i<=31;i++){ int x=p[i]; for(int j=1;x<=n;j++,x*=p[i])q.push({x,p[i],j,i-1}); } while(k--){ node tmp=q.top(); q.pop(); if(!k)return cout<<tmp.val,0; if(tmp.k>1)for(int i=1;i<=tmp.last;i++) q.push({tmp.val/tmp.maxn*p[i],tmp.maxn,tmp.k-1,i}); } return 0; }
这篇关于2021.08.01 P4359 伪光滑数(二叉堆)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)