P1621 集合

传送门

解题思路

因为是在[a,b]范围内将两个拥有大于等于P的公共质因数的整数进行合并，关于质数的操作我们很容易会联想到素数筛，实际上就是这样，我们先通过欧拉筛，然后我们找到第一个大于等于a的质数，然后将[a,b]范围内的该质数的倍数进行合并操作，最后从a到b数一下有多少个分类即可

Code

#include
using namespace std;
#define endl "\n"

const int N = 100005;

int primes[N];
bool vis[N];
int b,a,p;
int fa[N];


void init() {
	for(int i = 1;i