点这里看题目。
本题有很多直接构造伪光滑数的做法，这些去网上搜一搜就好了。
这里讲一个很暴力但又很有意义的做法。
考虑到限制的特殊性，需要知道指数和，我们可以写出下面这个状态：
\(f(i,k)\)：最大质因子刚好为 \(p_i\) ，指数和为 \(k\) 的数集，此时应有 \(k\le \lfloor\log_{p_i}n\rfloor\) 。（ \(p_i\) 即为第 \(i\) 个质数）
没错，我们要对数集进行 DP ！
首先定义一下要用的集合运算：
定义辅助状态：
\(g(i,k)\)：最大质因子小于等于 \(p_i\) ，指数和为 \(k\) 的数集。
然后就可以发现一个转移：
考虑最终的操作。此时我们就可以把所有的可用的 \(f\) 丢到堆里面，按照集合中最大值排序。我们不断地取出最大值最大的 \(f\) ，删除最大值并把它丢回堆里面去。那么?第 \(k\) 次取出的时候就应该是答案。
思考一下我们要干的事情。我们需要使用既能查询最值，又可以合并的数据结构。显然我们需要用到可并堆。此外，如果我们单独将 \(f\) 全部存下来，空间就会爆炸。而 \(f\) 和 \(g\) 里面必然会有很多重复的值，我们可以考虑使用可持久化可并堆，极大地优化空间。
顺带一提，极大优化空间就是指你还需要开 1.6e7 的空间
因此，写一个全局的可持久化可并堆， \(f\) 和 \(g\) 就相当于指向了一些节点。统计答案时候的堆也可以用 <值，根> 二元组来表示。
这样做的时间复杂度就是 ..... \(O(k\log_2?)\) ，我实在是算不出来这个复杂度了。
这个算法最妙的地方就是它直接对集合进行 DP ，比较新颖，也相当暴力。如果运气好集合小就可以尝试一下它。
不晓得出了什么问题，虽然可以过题，但是会有玄学错误。
建议不要参考我的代码学习。
#include <queue>
#include <cstdio>
#include <cstring>
#include <assert.h>
#include <utility>
using namespace std;
typedef unsigned long long LL;
typedef pair<LL, int> heap;
const int MAXP = 50, MAXS = 1.6e7 + 5, MAXLOG = 70;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > ‘9‘ || s < ‘0‘ ){if( s == ‘-‘ ) f = -1; s = getchar();}
while( s >= ‘0‘ && s <= ‘9‘ ){x = ( x << 3 ) + ( x << 1 ) + ( s - ‘0‘ ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( ‘-‘ ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + ‘0‘ );
}
template<typename _T>
void swapp( _T &x, _T &y )
{
_T t = x; x = y, y = t;
}
priority_queue<heap> q;
int f[MAXP][MAXLOG], g[MAXLOG];
// f 表示最大质因子为 i ，次数和为 j 的数集。
// g 表示 f 在第一维上的前缀和。
LL val[MAXS], tag[MAXS];
int lch[MAXS], rch[MAXS], deg[MAXS], dist[MAXS];
int stk[MAXS], top;
LL pw[MAXP][MAXLOG];
int lg[MAXP];
int prime[MAXP], pn;
bool isPrime[130];
LL N; int K, tot, cnt;
void EulerSieve( const int siz )
{
for( int i = 2 ; i <= siz ; i ++ )
{
if( ! isPrime[i] ) prime[++ pn] = i;
for( int j = 1 ; j <= pn && i * prime[j] <= siz ; j ++ )
{
isPrime[i * prime[j]] = true;
if( ! ( i % prime[j] ) ) break;
}
}
}
void init()
{
EulerSieve( N < 127 ? N : 127 );
for( int i = 1 ; i <= pn ; i ++ )
{
for( LL tmp = 1 ; tmp <= N ; tmp *= prime[i], lg[i] ++ );
lg[i] --, pw[i][0] = 1;
for( int j = 1 ; j <= lg[i] ; j ++ )
pw[i][j] = pw[i][j - 1] * prime[i];
}
}
int merg( int, int );
void copy( int, int );
void normalize( const int );
int pop( const int u )
{
normalize( u );
return merg( lch[u], rch[u] );
}
int newNode( const int nVal = 0 )
{
int cur;
if( top ) cur = stk[top --];
else cur = ++ tot;
val[cur] = nVal, tag[cur] = 1;
lch[cur] = rch[cur] = deg[cur] = dist[cur] = 0;
return cur;
}
int times( int u, LL delt )
{
if( ! u ) return u;
int cur = newNode(); copy( cur, u );
val[cur] *= delt, tag[cur] *= delt;
return cur;
}
void link( int &u, const int nw )
{
if( nw == u ) return ;
if( u && ! ( -- deg[u] ) )
stk[++ top] = u;
++ deg[u = nw];
}
void copy( int u, int fr )
{
if( ! fr ) { u = fr; return ; }
normalize( u );
normalize( fr );
val[u] = val[fr], tag[u] = tag[fr];
link( lch[u], lch[fr] );
link( rch[u], rch[fr] );
dist[u] = dist[fr];
}
void normalize( const int u )
{
if( ! u || tag[u] == 1 ) return;
link( lch[u], times( lch[u], tag[u] ) );
link( rch[u], times( rch[u], tag[u] ) );
tag[u] = 1;
}
int merg( int u, int v )
{
if( ! u || ! v ) return u + v;
if( val[u] < val[v] ) swapp( u, v );
normalize( u );
int cur = newNode(); copy( cur, u );
link( rch[cur], merg( rch[u], v ) );
if( dist[rch[cur]] > dist[lch[cur]] )
swapp( rch[cur], lch[cur] );
dist[cur] = dist[rch[cur]] + 1;
return cur;
}
signed main()
{
read( N ), read( K );
dist[0] = -1;
init();
link( g[0], newNode( 1 ) );
for( int i = 1 ; i <= pn ; i ++ )
for( int j = lg[i] ; j ; j -- )
{
for( int k = 1 ; k <= j ; k ++ )
link( f[i][j], merg( f[i][j], times( g[j - k], pw[i][k] ) ) );
link( g[j], merg( g[j], f[i][j] ) );
q.push( heap( val[f[i][j]], f[i][j] ) );
}
LL ans = 0;
while( ! q.empty() && K )
{
heap h = q.top();
q.pop();
ans = h.first;
link( h.second, pop( h.second ) );
if( h.second )
q.push( heap( val[h.second], h.second ) );
K --;
}
write( ans ), putchar( ‘\n‘ );
return 0;
}
原文：https://www.cnblogs.com/crashed/p/13449441.html