P1621 集合

题目描述

现在给你一些连续的整数，它们是从A到B的整数。一开始每个整数都属于各自的集合，然后你需要进行一下的操作：

每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于P的公共质因数，那么把它们所在的集合合并。

反复如上操作，直到没有可以合并的集合为止。

现在Caima想知道，最后有多少个集合。

输入输出格式

输入格式：

一行，三个整数A,B,P。

【数据规模】

A≤B≤100000；

2≤P≤B。

输出格式：

一个数，表示最终集合的个数。

---

考虑枚举质数， 然后暴力在 \([L, R]\) 中合并某一质数的倍数即可

质数表在这个范围怎么搞都可以， 集合合并的话用并查集

处理的话将区间内第一个质数的倍数作为代表合并即可

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

int RD(){

	int flag = 1, out = 0;char c = getchar();

	while(c < '0' || c > '9'){if(c == '-')flag = -1;c = getchar();}

	while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

	return flag * out;

	}

const int maxn = 100019;

int L ,R, P;

int prime[maxn], tot;

bool isprime[maxn];

void find_prime(int n){

	for(int i = 2;i <= n;i++){

		if(!isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && prime[j] * i <= n;j++){

			isprime[prime[j] * i] = 1;

			if(i % prime[j] == 0)break;

			}

		}

	}

int father[maxn];

int findfather(int v){

	if(father[v] == v)return v;

	return father[v] = findfather(father[v]);

	}

void Union(int a, int b){

	int faA = findfather(a), faB = findfather(b);

	if(faA != faB)father[faA] = faB;

	}

int main(){

	L = RD(); R = RD(); P = RD();

	find_prime(R);

	for(int i = L;i <=  R;i++)father[i] = i;

	int num = R - L + 1;

	int p = 1;while(prime[p] < P)p++;

	for(int i = p;i <= tot;i++){

		int j = 1;

		while(prime[i] * j < L)j++;

		int now = prime[i] * j++;

		for(j;j * prime[i] <= R;j++){

			if(findfather(j * prime[i]) != findfather(now)){

				num--;

				Union(j * prime[i], now);

				}

			}

		}

	printf("%d\n", num);

	return 0;

	}