乱搞。

Description

若一个大于 $1$ 的整数 $M$ 的质因数分解有 $k$ 项，其最大的质因子为 $a_k$，并且满足 ${a_k}^k \leq N$, $a_k<128$，我们就称整数 $M$ 为 $N$-伪光滑数。

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

Solution

Sol. 1

在堆中插入最大素因子为每个素数的四元组$(v, p, fir, sec)$, 分别是当前数值, 最小素数编号, 最小素数指数, 次小素数指数.

每次堆中取最大值, 有两种扩展, 把一个次小素因子换成最小素因子/把一个最小素因子换成更小的下一个素因子.

可以证明这样能不重不漏地遍历所有数.

取走$k - 1$次即可. 再取堆顶就是答案了.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n; int k;

struct node {
  ll cur; int pr, fir, sec;
  inline bool operator<(const node &rhs) const {
    return cur < rhs.cur;
  }
};
priority_queue<node> q;

int npr[150], cnt;
ll pr[50];
void euler() {
  for (int i = 2; i < 128; ++i) {
    if (!npr[i]) pr[++cnt] = i;
    for (int j = 1; j <= cnt && i * pr[j] < 128; ++j) {
      npr[i * pr[j]] = 1;
      if (!(i % pr[j])) break;
    }
  }
}


int main() {
  scanf("%lld%d", &n, &k);
  euler();
  pr[0] = 1;
  node y;
  for (int i = 1; i <= 31; ++i) {
    ll pw = 1; int j = 0;
    for (; pw <= n / pr[i]; j++, pw *= pr[i]);
    node x;
    x.cur = pw; x.pr = i; x.fir = j - 1; x.sec = 0;
    q.push(x);
  }
  while (--k) {
    node x = q.top(); q.pop();
    if (x.pr) {
      ll tmp = x.cur / pr[x.pr] * pr[x.pr - 1];
      y.cur = tmp; y.pr = x.pr - 1; y.fir = 1; y.sec = x.fir - 1;
      q.push(y);
    }
    if (x.sec) {
      ll tmp = x.cur / pr[x.pr + 1] * pr[x.pr];
      y.cur = tmp; y.pr = x.pr; y.fir = x.fir + 1; y.sec = x.sec - 1;
      q.push(y);
    }
  }
  y = q.top();
  printf("%lld",y.cur);
  return 0;
}

Sol. 2

是一个DP做法, 大概就是维护一个最大素因子为$i$, 有$k$个素因子的全体元素组成的集合, 转移支持集合乘, 集合取并, 集合最大值.

可持久化可并堆.

然而懒得写了.