题解

可持久化可并堆

用\(f[i,j]\)表示最大的质数标号为i，然后有j个质数乘起来

用\(g[i,j]\)表示\(\sum_{k = 1}^{i}f[k,j]\)

转移是

\(f[i,j] = \sum_{k= 1}^{j} g[i - 1,j - k] * p_{i}^{k}\)

\(g[i,j] += f[i,j]\)

这就要资瓷两个集合的合并了

可是集合显然非常大，我们可以用可持久化来帮助完成这件事，就完成了

代码

#include 
    
     #define enter putchar('\n')#define space putchar(' ')#define pii pair
     
      #define fi first#define se second#define MAXN 1000005#define pb push_back#define mp make_pair#define eps 1e-8//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 + c - '0';        c = getchar();    }}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) out(x / 10);    putchar('0' + x % 10);}int64 N;int K,prime[105],tot;bool nonprime[205];int64 pw[105];struct node {    node *lc,*rc;    int64 mul,val;    int dis;}pool[17000000],*tail = pool;struct set_node {    int64 val;node *rt;    set_node(){}    set_node(int64 _v,node *r) {        val = _v;rt = r;    }    friend bool operator < (const set_node &a,const set_node &b) {        return a.val > b.val;    }    friend bool operator == (const set_node &a,const set_node &b) {        return a.val == b.val && a.rt == b.rt;    }};node *g[105],*f[105];set
        
          S;node *Newnode(int64 v) {    node *res = tail++;    res->mul = 1;res->val = v;    res->lc = res->rc = NULL;    res->dis = 0;    return res;}int getdist(node *p) {    return p ? p->dis : -1;}node* addlazy(node *u,int64 val) {    if(!u) return NULL;    node *res = tail++;    *res = *u;    res->val *= val;    res->mul *= val;    return res;}void push_down(node *&u) {    if(u->mul != 1) {        u->lc = addlazy(u->lc,u->mul);        u->rc = addlazy(u->rc,u->mul);        u->mul = 1;    }}node *Merge(node *A,node *B) {    if(!A) return B;    if(!B) return A;    if(A->val < B->val) swap(A,B);    push_down(A);    node *res = tail++;    *res = *A;    res->rc = Merge(A->rc,B);    if(getdist(res->rc) > getdist(res->lc)) swap(res->lc,res->rc);    res->dis = getdist(res->rc) + 1;    return res;}void Solve() {    read(N);read(K);    for(int i = 2 ; i <= 128 ; ++i) {        if(!nonprime[i]) {            prime[++tot] = i;            for(int j = 2 ; j <= 128 / i ; ++j) {                nonprime[i * j] = 1;            }        }    }    for(int i = 0 ; i <= 100 ; ++i) g[i] = NULL;    g[0] = Newnode(1);    for(int i = 1 ; i <= tot ; ++i) {        int cnt = 0;int64 t = N;        while(t >= prime[i]) {t /= prime[i];++cnt;}        pw[0] = 1;        for(int k = 1 ; k <= cnt ; ++k) pw[k] = pw[k - 1] * prime[i];        for(int k = 1 ; k <= cnt ; ++k) {            f[k] = NULL;            for(int h = 1 ; h <= k ; ++h) {                f[k] = Merge(f[k],addlazy(g[k - h],pw[h]));            }        }        for(int k = 1 ; k <= cnt ; ++k) g[k] = Merge(g[k],f[k]);    }    node *rt = NULL;    for(int i = 1 ; i <= 100 ; ++i) rt = Merge(rt,g[i]);    S.insert(set_node(rt->val,rt));    for(int i = 1 ; i < K ; ++i) {        set_node p = *S.begin();        S.erase(S.begin());        push_down(p.rt);        if(p.rt->lc) S.insert(set_node(p.rt->lc->val,p.rt->lc));        if(p.rt->rc) S.insert(set_node(p.rt->rc->val,p.rt->rc));        while(S.size() > K - i) S.erase(--S.end());    }    out((*S.begin()).val);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}