P1621. 集合

发表于 2023-11-10 分类于洛谷阅读次数： Waline：本文字数： 331 阅读时长 ≈ 1 分钟

考点

并查集

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e5 + 10;
int a, b, p, cnt, fa[LEN], prim[LEN];
bool vis[LEN];

int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}

void join(int x, int y) {
  int a = find(x), b = find(y);
  fa[a] = b;
}

void init() {
  //线性筛
  for (int i = 2; i <= b; ++i) {
    if (!vis[i]) prim[cnt++] = i;
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * prim[j] > b) continue;
      vis[i * prim[j]] = true;
      if (i % prim[j] == 0) break;
    }
  }
  for (int i = 1; i <= b; ++i) fa[i] = i;
}

int main() {
  cin >> a >> b >> p;
  init();
  for (int i = 0, x; i < cnt; ++i) {
    if (prim[i] < p) continue;
    x = prim[i];
    for (int j = 1; j * x <= b; ++j) {
      if (j * x >= a) join(x, x * j);
    }
  }
  int ans = 0;
  for (int i = a; i <= b; ++i) {
    if (fa[i] == i) ++ans;
  }
  cout << ans;
  return 0;
}