[bzoj 4524--Cqoi2016]僞光滑數

若一個大于1的整數M的質因數分解有k項，其最大的質因子為Ak，并且滿足Ak^K<=N,Ak<128，我們就稱整數M為N-僞光滑數。現在給出N，求所有整數中，第K大的N-僞光滑數。

這種問題首先發現一個數是否是僞光滑數隻跟它的最大的質因子和分解後的項數有關，而隻有31種質因子，是以總共的類别是有限的（把最大的質因子和分解後的項數都相同的歸為一類）。

那根據套路開個大根堆，一開始把所有類别的最大值放進去，每取top一次從大到小拓展同類别的數，當然要保證一個數隻會被拓展一次。那麼結果就為第k次取top的結果。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
struct node
{
    int cnt[35],id,p;long long d;
    node(){memset(cnt,0,sizeof(cnt));}
};
priority_queue<node>q;
bool operator <(node a,node b){return a.d<b.d;}
int sta[35]={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()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    long long n;int num;
    scanf("%lld%d",&n,&num);num--;
    for(int i=0;i<31;i++)
    {
    	node ul;ul.cnt[i]=1,ul.d=sta[i],ul.id=ul.p=i;
    	while(ul.d<=n){q.push(ul);ul.d*=sta[i],ul.cnt[i]++;}
    }
    while(num--)
    {
    	node uf=q.top();q.pop();
    	for(int i=1;i<=uf.id;i++)
    	{
    		node wy=uf;bool bk=false;
    		if(i==uf.p)
            {
                 if(uf.cnt[i]>1)bk=true;
            }
            else if(uf.cnt[i])bk=true;
    		if(bk==true){wy.d=uf.d/sta[i]*sta[i-1],wy.id=i;wy.cnt[i]--,wy.cnt[i-1]++;q.push(wy);}
    	}
    }printf("%lld\n",q.top().d);
    return 0;
}