题面在这里
观察发现\(K\)比较小，可以依次求出前\(K\)大的N-伪光滑数
显然可以由\(已经存在的数/最大质因数*较小质数\)得到新的伪光滑数
记录四元组\((x,p,t,pre)\)分别表示当前数是x，最大质因数是p，次数t，能乘的最大质数
这样扩展，随着t减小，pre是递减的，做到了不重不漏
初始当然是对每个小于128的质数都放入1次,2次,3次……
示例程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=130;
ll n,k;
struct data{
ll x;int p,t,pre;
data () {}
data (ll _x,int _p,int _t,int _pre):x(_x),t(_t),pre(_pre),p(_p) {}
inline bool operator<(const data&b)const {return x<b.x;}
};
priority_queue<data> Q;
int p[maxn]; bool vis[maxn];
void makep(int n){
for (int i=2;i<=n;i++){
if (!vis[i]) p[++p[0]]=i;
for (int j=1;j<=p[0]&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if (i%p[j]==0) break;
}
}
}
int main(){
scanf("%lld%lld",&n,&k);k--;
makep(128);
for (int i=1;i<=p[0];i++){
int t=1;ll x=p[i];
while (x<=n) Q.push(data(x,p[i],t,i-1)),x*=p[i],t++;
}
while (k--){
data m=Q.top();Q.pop();
if (m.t==1) continue;
for (int i=1;i<=m.pre;i++)
Q.push(data(m.x/m.p*p[i],m.p,m.t-1,i));
}
printf("%lld",Q.top().x);
return 0;
}
|
