【BZOJ4524】[Cqoi2016]伪光滑数
Description
若一个大于1的整数M的质因数分解有k项，其最大的质因子为A，并且满足A^K<=N,A<128，我们就称整数M为N-伪光滑数。现在给出N，求所有整数中，第K大的N-伪光滑数。
Input
只有一行，为用空格隔开的整数N和K
2 ≤ N ≤ 10^18， 1 ≤ K ≤ 800000，保证至少有 K 个满足要求的数
Output
只有一行，为一个整数，表示答案。
Sample Input
12345 20
Sample Output
9167
题解：先打表打出前31个质数，然后枚举每个质数作为最大质因子，算出此时最多能有多少项，那么此时的最大值显然=这个质数^项数。我们将其扔到堆中。
然后我们要做的就是每次从堆中取出最大的数，将他的一个质因子变小，然后再扔到队列中去，重复k次。并且我们要保证我们的取法不会出现遗漏和重复。这就是一个套路了。我们试图模拟搜索的过程。在搜索时，假如我们已经取了一些质数，他们的积为val，那么我们可以再取一个val的最小质因子，或者继续考虑下一个更小的质因子。现在我们要模拟这个方法：
我们维护四元组(val,mn,first,second)代表当前的数，最小的质因子编号，最小的质因子次数，次小的质因子次数。那么如果我们从堆中取出一个数，我们可以用一个最小质因子来换一个次小质因子，或者用最小质因子的下一个质数来替换最小质因子。容易发现这样是可以做到不重不漏的。由于每次我们只往堆中扔进去2个数，所以时间复杂度就是$O(Klog_K)$的。（看见那些时间复杂度是$O(31*Klog_K)$的我就想笑~）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
int m;
ll n;
int p[]={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};//31
struct node
{
ll val;
int mn,lst,sec;
bool operator < (const node &a) const
{
return val<a.val;
}
};
priority_queue<node> q;
int main()
{
scanf("%lld%d",&n,&m);
register node x,y;
register int i,j;
for(i=1;i<=31;i++)
{
ll tmp;
for(tmp=1,j=0;tmp<=n/p[i];j++,tmp*=p[i]);
x.val=tmp,x.mn=i,x.lst=j-1,x.sec=0;
q.push(x);
}
while(--m)
{
x=q.top(),q.pop();
if(x.mn)
{
y.val=x.val/p[x.mn]*p[x.mn-1],y.mn=x.mn-1,y.lst=1,y.sec=x.lst-1;
q.push(y);
}
if(x.sec)
{
y.val=x.val/p[x.mn+1]*p[x.mn],y.mn=x.mn,y.lst=x.lst+1,y.sec=x.sec-1;
q.push(y);
}
}
x=q.top();
printf("%lld",x.val);
return 0;
}