[CQOI2016]伪光滑数

题目描述

若一个大于1的整数M的质因数分解有k项，其最大的质因子为A，并且满足A^K<=N,A<128，我们就称整数M为N-伪

光滑数。现在给出N，求所有整数中，第K大的N-伪光滑数。

题解

题面的k意思是将这个数质因数分解后所有的质因子的指数和。

我们先把128以内的所有素数找出来，然后做一个dp。

我们令dp[i][j]表示当前数的最大的质因子为p[i]，当前所有素因子的指数和为j的数的集合。

我们再令g[i][j]表示当指数和位j时，所有最大质因子小于等于p[i]的数的集合。

然后我们可以合并集合。

f[i][j]=∑g[i-1][j-k]*p[i]

g[i][j]=g[i-1][j]+f[i][j]

然后我们可以用函数式可并堆来维护所有的转移，在开一个全局的堆来维护所有的f。

然后一直弹堆顶就可以了。

注意pushdown

代码

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

typedef long long ll;

int tot,prime[],K,f[][],g[][];

ll n;

bool vis[];

inline ll rd(){

    ll x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

struct node{

    int i,j;ll val;

    node(int ii=,int jj=,ll v=){i=ii;j=jj;val=v;}

    inline bool operator <(const node &b)const{return val<b.val;}

};

priority_queue<node>q;

struct tree{

    ll val,la;int l,r,d;

    tree(ll xx=,ll yy=,int lx=,int rx=,int dd=){val=xx;la=yy;l=lx;r=rx;d=dd;}

}tr[];

inline int newnode(int x,ll y){

    if(!x)return ;

    int p=++tot;

    tr[p]=tr[x];tr[p].val=tr[p].val*y;tr[p].la=tr[p].la*y;

    return p;

}

inline void pushdown(int cnt){

    if(tr[cnt].la!=){

        tr[cnt].l=newnode(tr[cnt].l,tr[cnt].la);

        tr[cnt].r=newnode(tr[cnt].r,tr[cnt].la);

        tr[cnt].la=;

    }

}

int merge(int x,int y){

    if(!x||!y)return x|y;

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

    pushdown(x);

    int p=newnode(x,);

    tr[p].r=merge(tr[p].r,y);

    if(tr[tr[p].l].d<tr[tr[p].r].d)swap(tr[p].l,tr[p].r);

    tr[p].d=tr[tr[p].r].d+;

    return p;

}

inline void prework(){

    int k;

    for(int i=;i<=;++i){

        if(!vis[i])prime[++prime[]]=i;

        for(int j=;j<=prime[]&&(k=i*prime[j])<=;++j){

            vis[i*prime[j]]=;

            if(i%prime[j]==)break;

        }

    }

}

int main(){

    cin>>n>>K;

    prework();

    f[][]=g[][]=tot=tr[].val=tr[].la=;

    for(int i=;i<=prime[];++i){

        f[i][]=g[i][]=;

        for(ll pr=prime[i],j=;pr<=n&&pr>;++j,pr=pr*prime[i]){

            f[i][j]=;

            for(ll prm=prime[i],k=;k<=j;++k,prm=prm*prime[i]){

                f[i][j]=merge(f[i][j],newnode(g[i-][j-k],prm));

            }

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

            q.push(node(i,j,tr[f[i][j]].val));

        }

    }

    ll ans=;

    while(K--){

        node x=q.top();q.pop();

        ans=x.val;

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

        f[x.i][x.j]=merge(tr[f[x.i][x.j]].l,tr[f[x.i][x.j]].r);

        q.push(node(x.i,x.j,tr[f[x.i][x.j]].val));

    }

    printf("%lld",ans);

    return ;

}