【BZOJ4524】[CQOI2016] 伪光滑数(堆的套路题)

点此看题面

大致题意: 设一个数质因数分解后有(k)项,其中最大质因数为(p_k)。若称这个数为N-伪光滑数,当且仅当满足(p_k^kle N,p_k<128)。现在求第(K)大的N-伪光滑数。

前言

(Jan 27th)刷题计划(1/6),算法标签:堆、Hash(完全不知道为什么会有Hash)、平衡树(可能有人闲得无聊手写个平衡树来当堆用......)。

感觉自己真的不行了,这么套路的题,先是看成第(K)小结果对着样例懵了半天,然后又因为一个智障的(bug)调了快(20)分钟。

预处理

一个显然的性质,当能取到最大值时,必然是(p_1=p_2=...=p_k),即这个数恰好为(p_k)的幂。

因此我们先给小于(128)的质数打个表出来,然后枚举质数,把它所有小于等于(N)的幂都扔到一个大根堆里面。

对于每一个数,我们需要记下(4)个信息:最大质因子的编号(p)、最大能新取的质因子的编号(m)、这个数的值(v)、这个数中(p_k)的次数(t)

质因子的编号,就是指这是第几个质数。

对于(P_i^x)(即第(i)个质数的(x)次幂),我们初始化(p=i,m=i-1,v=P_i^x,t=j)

至于什么是最大能新取的质因子,以及这(4)个信息存下来有什么用,我们放后面再说。

堆套路

(i)次操作,我们取出堆顶的元素,便得到了第(i)大的N-伪光滑数。

然后我们要考虑,根据当前得到的这个第(i)大的数,去生成更小的数。

如果当前最大质因子仅剩一个,即(t=1)了,我们就不予操作(不然就没有最大质因子了)。

否则,我们在(1sim m)的范围内,枚举一个新的质因子(P_j),用于替换当前的一个最大质因子。

于是就得到一个新数,新的参数分别为(p'=p,m'=j,v'=frac v{P_p} imes P_j,t'=t-1)

因此,我们就不难明白什么是最大能新取的质因子:为了保证得到的数不重复。我们每次选择的新的质因子,一定不能大于之前所选过的任意质因子,这样就能保证每一个数都只可能通过唯一一种对应方式生成。

经过(K-1)次操作之后,此时堆顶元素的值便是第(K)大的N-伪光滑数了。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define K 800000
#define LL long long
using namespace std;
LL n;int k,Pt,P[128];
struct data
{
	int p,m;LL v,t;I data(CI x=0,CI s=0,Con LL& u=0,Con LL& k=0):p(x),m(s),v(u),t(k){}
	I bool operator < (Con data& o) Con {return v<o.v;}
};priority_queue<data> Q;
I bool IsP(CI x) {RI i;for(i=2;i*i<=x;++i) if(!(x%i)) return false;return true;}
int main()
{
	RI i,j;LL g;scanf("%lld%d",&n,&k);
	for(i=2;i^128&&i<=n;++i) if(IsP(i))//给质数打表
		for(P[++Pt]=g=i,j=1;g<=n;g*=i,++j) Q.push(data(Pt,Pt-1,g,j));//把质数所有小于等于n的幂扔入堆中
	data t;for(i=1;i^k;++i) if(t=Q.top(),Q.pop(),t.t>1)//当最大质因子存在大于1个时,用它来生成新数
		for(j=t.m;j;--j) Q.push(data(t.p,j,t.v/P[t.p]*P[j],t.t-1));//枚举一个新的质因子替换一个最大质因子
	return printf("%lld",Q.top().v),0;
}
原文地址:https://www.cnblogs.com/chenxiaoran666/p/BZOJ4524.html