这题很多人都用DP+可并堆

也有很多人暴力上堆 复杂度是$klogk$乘上128以内的质因数个数，约30(不过实际效果挺好的)

然而直接上堆，可以做到$2*k$次$push$,$k$次$pop$ 。

首先枚举所有可能的最大质因子及质因子分解的项数

这样题目的限制就没了，每次拓展时就可以除掉一个质因数再乘上一个质因数(只要别把最大质因子除没了)

考虑如何可以使得所有数会被拓展到且只会被拓展到一次

一个想法就是每次拓展时除掉最小质因子再乘上其前驱(比它小的最大质数)

但对于一个有多个质因子的数这样还是不能拓展到

所以再加一个方向:除掉最大质因子再乘上最小质因子

这样就ok了。

$O(klogk)$

拿到了bzoj rank3。 (下面这个直接用priority_queue的就能拿rank5，后来我手写了二叉堆。 我还写了配对堆，但不知道为什么慢了一倍多)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

const int N=128;
int pr[N],cnt;
struct point
{
    ll a;
    int b,c,d;
    point( ll a , int b , int c , int d ) : a( a ) , b( b ) , c( c ) , d( d ) {}
};
bool operator <(const point &p1,const point &p2)
{
    return p1.a<p2.a;
}
priority_queue<point> h;

bool is_p(int x)
{
    for(int i=2;i*i<=x;++i)
        if(x%i!=0) return 0;
    return 1;
}

int main()
{
    //freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
    ll n;int k;
    cin>>n>>k;
    rep(i,2,N)
    if(is_p(i))
    {
        pr[++cnt]=i;
        ll a=1;
        for(int j=1;a<=n/i;++j)
        {
            a*=i;
            h.push( point(a,i,0,0) );
            if(cnt>1&&j>1)
                h.push( point(a/i*pr[cnt-1],i,j-1,cnt-1) );
        }
    }

    while(--k)
    {
        point now=h.top();
        h.pop();
        if(now.d>1)
            h.push( point( now.a/pr[now.d]*pr[now.d-1],now.b,now.c,now.d-1 ) );
        if(now.c>1)
            h.push( point( now.a/now.b*pr[now.d],now.b,now.c-1,now.d ) );
    }
    cout<<h.top().a;
}