题目描述

若一个大于1的整数M的质因数分解有k项，其最大的质因子为A

_k，并且满足A

_k^K<=N,A

_k<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]^k

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

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

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

注意pushdown

代码

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;int tot,prime[33],K,f[33][65],g[33][65];ll n;bool vis[130];inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
    if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct node{    int i,j;ll val;    node(int ii=0,int jj=0,ll v=0){i=ii;j=jj;val=v;}    inline bool operator <(const node &b)const{
    return val
          
           
            q;struct tree{ ll val,la;int l,r,d; tree(ll xx=0,ll yy=1,int lx=0,int rx=0,int dd=0){val=xx;la=yy;l=lx;r=rx;d=dd;}}tr[16000002];inline int newnode(int x,ll y){ if(!x)return 0; 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!=1){ tr[cnt].l=newnode(tr[cnt].l,tr[cnt].la); tr[cnt].r=newnode(tr[cnt].r,tr[cnt].la); tr[cnt].la=1; }}int merge(int x,int y){ if(!x||!y)return x|y; if(tr[x].val
            
             >n>>K; prework(); f[0][0]=g[0][0]=tot=tr[1].val=tr[1].la=1; for(int i=1;i<=prime[0];++i){ f[i][0]=g[i][0]=1; for(ll pr=prime[i],j=1;pr<=n&&pr>0;++j,pr=pr*prime[i]){ f[i][j]=0; for(ll prm=prime[i],k=1;k<=j;++k,prm=prm*prime[i]){ f[i][j]=merge(f[i][j],newnode(g[i-1][j-k],prm)); } g[i][j]=merge(g[i-1][j],f[i][j]); q.push(node(i,j,tr[f[i][j]].val)); } } ll ans=0; 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 0;}