题解 | #漂亮数#

H. 漂亮数

线性筛加打表.

如果处理出以内,每个数是否是漂亮数,然后做个前缀和,就可以回答询问了.

怎么处理呢? 线性筛的过程中标记一下就可以了.

#include <bits/stdc++.h>
using namespace std;
#ifdef BACKLIGHT
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 1e8 + 5;

int pcnt, p[N], c[N];
bool is[N];
void euler_seive(int n = N - 1) {
  pcnt = 0;
  for (int i = 0; i <= n; ++i) is[i] = true;
  for (int i = 2; i <= n; ++i) {
    if (is[i]) p[pcnt++] = i;
    for (int j = 0; j < pcnt; ++j) {
      int64_t nxt = 1ll * p[j] * i;
      if (nxt > n) break;
      is[nxt] = false;
      if (is[i]) c[nxt] = 1;
      if (i % p[j] == 0) break;
    }
  }
  for (int i = 1; i < N; ++i) c[i] += c[i - 1];
}

void solve(int Case) {
  int l, r;
  cin >> l >> r;
  cout << c[r] - c[l - 1] << endl;
}

int main() {
#ifdef BACKLIGHT
  freopen("a.in", "r", stdin);
#endif
  euler_seive();
  int T = 1;
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) solve(t);
  return 0;
}