洛谷 P1621. 集合
原题链接
中等
作者:
我是java同学
,
2024-01-26 17:03:57
,
所有人可见
,
阅读 29
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a, b, _p;
int p[N];
int primes[N], vis[N];
bool st[N];
int cnt1, cnt2;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void get_primes(int n) {
for (int i = 2; i <= n; i ++ ) {
if (!st[i]) primes[cnt1 ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ ) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
cin >> a >> b >> _p;
for (int i = a; i <= b; i ++ ) p[i] = i;
get_primes(b);
for (int i = _p; i <= b; i ++ )
if (!st[i]) vis[cnt2 ++ ] = i;
for (int i = 0; i < cnt2; i ++ ) {
int s = 0;
while (s * vis[i] < a) s ++ ;
while (vis[i] * (s + 1) <= b) {
int x = find(vis[i] * s), y = find(vis[i] * (s + 1));
if (x != y) p[x] = y;
s ++;
}
}
int res = 0;
for (int i = a; i <= b; i ++ )
if (p[i] == i) res ++ ;
cout << res << endl;
return 0;
}