BZOJ 4524 伪光滑数

发表于 | 更新于

Link

标解是NOI式的一本正经 然而有POI式的闹着玩的做法

Solution

首先要读懂题目。。。 kk项指的是可以重复的项，也就是kk个质数相乘。。。。所以最大的项肯定就是形如pdp^d的数字了。。。 然后就要考虑采取POI式的堆+扩展法 表示数字为numnum，最大项为largelarge，最大项的个数为ltlt，还可以继续扩展的最大的数字为lastlast。 初始状态就把128128以内的单个质数的≤N\le N的幂全都弄到堆里面，然后弹KK次。如果堆顶的数字largelarge因子个数不为11，那就把堆顶数字的一个largelarge因子依次替换成prime[1:last]prime[1:last]的一个数字。 对于任意一个伪光滑数，可以把其中的因子从小到大依次替换，只会得到一条到初始状态的路径。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "lucida"
using std::priority_queue;
struct Node {
	int64 num;
	int large,lt,last;
	Node(int64 num,int large,int lt,int last):num(num),large(large),lt(lt),last(last) {}
	bool operator <(const Node &a) const {
		return num<a.num;
	}
};
int main() {
	freopen("input","r",stdin);
	int64 N;int K;is>>N>>K;
	static int prime[200],pcnt;
	priority_queue<Node> Q;
	for(int i=2;i<=128;++i) {
		static bool nope[200];
		if(!nope[i]) {
			prime[++pcnt]=i;
			int64 x=i,endx=N-N%i;
			for(int j=1;x<=endx;++j,x*=i)
				Q.push(Node(x,i,j,pcnt-1));
		}
		for(int j=1;j<=pcnt && i*prime[j]<=128;++j) {
			nope[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
	for(int i=1;i<=K-1;++i) {
		Node top=Q.top();Q.pop();
		if(top.lt!=1)
			for(int j=1;j<=top.last;++j)
				Q.push(Node(top.num/top.large*prime[j],top.large,top.lt-1,j));
	}
	int64 Ans=Q.top().num;
	os<<Ans<<'\n';
	return 0;
}