若一个数的质因数均不超过 ，称其为 -smooth number。

给定 求 以内 -smooth number 的个数。

• ；
• ，且 为质数。

样例 2 极具提示性。

注意到输入为 时，输出 ，大约只有 。

考虑暴搜。

但是 2e9 就算是 AT 神机估计也得跑个 6s 左右。

考虑 meet-in-middle，把 以内的质数分成 2 组，分别暴搜。

可以按质数从小到大交替分到两组中，平衡效率：

这样在 中暴搜时枚举量为 ，在 中暴搜时枚举量为 ；

也可以把 放到 中，这样枚举量分别为 和 。

统计答案时可以排序后双指针。

#include <bits/stdc++.h>
using namespace std;

array<uint32_t, 12> prime0{2, 5, 11, 17, 23, 31, 41, 47, 59, 67, 73, 83};
array<uint32_t, 13> prime1{3, 7, 13, 19, 29, 37, 43, 53, 61, 71, 79, 89, 97};

template <size_t Len>
void dfs(size_t cur, uint64_t val, uint64_t limit, uint32_t p,
         const array<uint32_t, Len> &prime, vector<uint64_t> &res) {
  if (cur == Len || prime[cur] > p)
    res.push_back(val);
  else
    for (; val <= limit; val *= prime[cur])
      dfs<Len>(cur + 1, val, limit, p, prime, res);
}

template <size_t Len>
vector<uint64_t> get_smooth(uint64_t limit, uint32_t p,
                            const array<uint32_t, Len> &prime) {
  vector<uint64_t> res;
  dfs<Len>(0, 1, limit, p, prime, res);
  sort(res.begin(), res.end());
  return res;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  uint64_t N;
  uint32_t p;
  cin >> N >> p;
  auto r1 = get_smooth(N, p, prime0);
  auto r2 = get_smooth(N, p, prime1);
  uint64_t cnt = 0;
  size_t pt = r2.size();
  for (uint64_t x : r1) {
    while (pt == 0 || r2[pt - 1] * x > N)
      --pt;
    cnt += pt;
  }
  cout << cnt << '\n';
  return 0;
}