Description：

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

$1\leqslant n\leqslant 10^{18},1\leqslant K\leqslant 800000$

Solution：

考虑一种方法，如果我们可以得到包含所有 $N-$ 伪光滑数的大根堆，那么我们只要 $pop$ 堆 $k$ 次就可以计算答案了，这个也是可以做到的。

设 $f[i][j]$ 表示最大质因子为 $p[i]$ ，分解出 $j$ 项的 $N-$ 伪光滑数的大根堆，转移为： $$ \begin{align} f[i][j]&=\sum_{k=0}^jg[i-1][j-k]\times p[i]^k\\ g[i][j]&=g[i-1][j]+f[i][j]\\ ans&=\sum_{i=0}^{31}\sum_{k=0}^{60}f[i][k](p[i]^k\leqslant N) \end{align} $$ 乘常数代表整体打 $tag$ ，加代表集合求并。

卡空间，因此不能用 $ans$ 把所有的都并起来而是要一个一个做。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

int K;

struct node

{

    int lc,rc,d;

    ll val,mul;

    node(int lc_ = 0,int rc_ = 0,ll val_ = 0,ll mul_ = 1)

    {

        lc = lc_;rc = rc_;val = val_;mul = mul_;

    }

}t[17000005];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void pushdown(int rt)

{

	if(t[rt].mul == 1)return;

    if(t[rt].lc)

    {

        int k = newnode();t[k] = t[t[rt].lc];t[rt].lc = k;

        t[t[rt].lc].val *= t[rt].mul;

        t[t[rt].lc].mul *= t[rt].mul;

    }

    if(t[rt].rc)

    {

        int k = newnode();t[k] = t[t[rt].rc];t[rt].rc = k;

        t[t[rt].rc].val *= t[rt].mul;

        t[t[rt].rc].mul *= t[rt].mul;

    }

    t[rt].mul = 1;

    return;

}

int merge(int x,int y)

{

    if(x == 0 || y == 0)return x + y;

    if(t[x].val < t[y].val)swap(x,y);

    int rt = newnode();t[rt] = t[x];

    pushdown(rt);

    t[rt].rc = merge(t[rt].rc,y);

    if(t[t[rt].lc].d < t[t[rt].rc].d)swap(t[rt].lc,t[rt].rc);

	t[rt].d = t[t[rt].rc].d + 1; 

    return rt;

}

void add(int rt,ll val)

{

    t[rt].val *= val;t[rt].mul *= val;

    return;

}

int f[32][61],g[32][61];

int p[32];

bool isprime[128];

int createnode(int rt,ll val)

{

    if(rt == 0)return 0;

    t[newnode()] = t[rt];add(ptr,val);

    return ptr;

}

struct res

{

	int i,j;ll val;

	friend bool operator < (const res& a,const res& b)

	{

		return a.val < b.val;

	}

};

priority_queue<res> ans;

int main()

{

    scanf("%lld%d",&n,&K);

    t[newnode()] = (node){0,0,1,1};

    f[0][0] = merge(f[0][0],ptr);

    g[0][0] = merge(g[0][0],f[0][0]);

    for(int i = 2;i < 128;++i)isprime[i] = true;

    for(int i = 2;i < 128;++i)

    {

        if(isprime[i])p[++p[0]] = i;

        for(int j = i * i;j < 128;j += i)isprime[j] = false;

    }

    for(int i = 1;i <= p[0];++i)

    {

        double cur = p[i];

        g[i][0] = g[i - 1][0];

        for(int j = 1;j <= 60 && cur <= n;++j,cur = cur * p[i])

        {

            ll pr = p[i];

            for(int k = 1;k <= j;++k,pr = pr * p[i])

            {

                int v = createnode(g[i - 1][j - k],pr);

                f[i][j] = merge(f[i][j],v);

            }

            g[i][j] = merge(g[i - 1][j],f[i][j]);

            ans.push((res){i,j,t[f[i][j]].val});

        }

    }

    ll v;

    for(int i = 1;i <= K;++i)

    {

		res k = ans.top();ans.pop();

		v = k.val;//cout << v << endl;

		pushdown(f[k.i][k.j]);

		f[k.i][k.j] = merge(t[f[k.i][k.j]].lc,t[f[k.i][k.j]].rc);

		ans.push((res){k.i,k.j,t[f[k.i][k.j]].val});

	}

	cout << v << endl;

    return 0;

}