NKOJ 3616(CQOI 2016) 伪光滑数（暴力堆/可持久化可并堆+dp）

发表于 |
字数统计: 977字 | 阅读时长 ≈ 4min

P3616【CQOI2016 Day2】伪光滑数

问题描述

若一个大于1的整数M的质因数分解有k项，其最大的质因子为$a_k$，并且满足$a_k^k$≤N，$a_k$<128，我们就称整数M为N-伪光滑数。
现在给出N，求所有整数中，第K大的N-伪光滑数。

输入格式

输入文件内容只有一行，为用空格隔开的整数N和K。

输出格式

输出文件内容只有一行，为一个整数，表示答案。

样例输入

12345 20

样例输出

9167

数据范围：
> 对于30%的数据，N≤$10^6$；
对于60%的数据，K≤$10^5$；
对于100%的数据，2≤N≤$10^{18}$，1≤K≤8*$10^5$，保证至少有K个满足要求的数。

算法一：贪心（暴力）+堆
观察题目，很容易想到可以将数分类，按照最大素因子来分类，如果最大素因子确定，那么最多可以有多少项也就确定了，因此，一个显然的贪心是，尽量取大的素数构造出来的数肯定是最大的。因此，先弄一个素数表，先把满足条件的素数的最大的次方加入一个大根堆，每次取出堆顶后，构造比他小的且最接近他的数，即除去一个最大素因子，再乘上一个比他小的素数。K-1次操作后取堆顶即可。

代码：

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
39
40
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll unsigned long long
using namespace std;
struct node{ll x,v,p;};
bool operator<(node a,node b)
{return a.v<b.v;}
priority_queue<node>Q;
ll n,k;
ll A[32]={1,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};
int main()
{
	ll i,t;node tmp,ttp;
	scanf("%lld%lld",&n,&k);
	for(i=1;i<32;i++)
	{
		t=1;
		while(t*A[i]<=n)t*=A[i];
		tmp.x=A[i];tmp.p=i;tmp.v=t;
		Q.push(tmp);
	}
	while(--k)
	{
		tmp=Q.top();
		Q.pop();
		ttp=tmp;
		if(tmp.v%tmp.x==0)
		{
			for(i=0;i<tmp.p;i++)
			{
				ttp.v=tmp.v/tmp.x*A[i];
				Q.push(ttp);
			}
		}
		while(Q.top().v==tmp.v)Q.pop();
	}
	cout<<Q.top().v;
}

算法二：可持久化可并堆+dp
这里先说明一个很简单思想，如果我们要解决求很大的数据中的第K大或第K小之类的问题，如果可以将这些数据归类，并且每一类数可以用一个堆来装起来，那么可以将这些堆放到一个全局堆中来维护，这样就可以解决问题了。
实际上，在上一个算法中，我们也是用的这样的方式来实现的，但是并没有将每一个堆实际上开出来，而是由于我们可以很直接的得到恰比某个数小的另一个数，所以采用了暴力枚举来替代堆。
因此，算法一实际上优于算法二。
算法二的核心在于，我们可以将数归类，用F[i,j]表示最大质因数为p[i]，可以分解成j项的数的集合，利用dp的手段我们可以递推的来将所有的F[i,j]算出来，为了实现，令G[i,j]表示F[i,j]的前缀和，于是
$f[i,j]=\sum_{k=1}^jg[i-1,j-k]*p[i]^k$
$g[i,j]=g[i-1,j]+f[i,j]$
而这里的集合显然可以用可持久化可并堆来维护，于是就可以将所有的F集合全部算出来，并且每一个都是大根堆，最后从全局堆取答案即可。

PS：实际上可以看出，算法二并不如算法一优秀，但是，如果遇到不能够很方便的将恰比某元素小的数找出来的话，算法二就有意义了。