【BZOJ 4524】[CQOI2016] 伪光滑数

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4524
正常题面及题解:http://blog.csdn.net/huanghongxun/article/details/51181809

解题报告

考虑按最大的质因子分类
那么每一次就是用次大的质因子去替换最大的质因子
再用堆来维护一下就好了

Code

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

LL n; int k;
int pri[]={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},tot=31;
struct Data{
	LL w; int k,MX,nxt;
	inline Data() {}
	inline Data(LL a, int b, int c, int d):w(a),k(b),MX(c),nxt(d) {}
	inline bool operator < (const Data &B) const {return w < B.w;}
};
priority_queue<Data> que; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	cin>>n>>k;
	for (int i=1;i<=tot;i++) {
		LL w = pri[i]; int t = 1;
		while (w <= n) {
			que.push(Data(w,t,i,i-1)),
			w *= pri[i]; t++;
		}
	}
	for (int j=1;j<k;j++) {
		Data t = que.top(); que.pop();
		if (t.k > 1) for (int i=1;i<=t.nxt;i++) {
			LL tmp = t.w / pri[t.MX] * pri[i];
			que.push(Data(tmp,t.k-1,t.MX,i));
		}
	}
	cout<<que.top().w;
	return 0;
}