题目描述Caima 给你了所有 ab 范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数如果这两个整数拥有大于等于 p 的公共质因数那么把它们所在的集合合并。重复如上操作直到没有可以合并的集合为止。现在 Caima 想知道最后有多少个集合。输入格式一行共三个整数 abp用空格隔开。输出格式一个数表示最终集合的个数。输入输出样例输入 #110 20 3输出 #17根据

#include #include #include #include using namespace std; const int N = 1e5+10; int a, b, p1; int sum, p[N];

int fifa(int x){ if(p[x] == x) return x; return p[x] = fifa(p[x]); }

void join(int x, int y){ int g = __gcd(x, y); if(g >= p1){ int fx = fifa(x); int fy = fifa(y); if(fx != fy){ sum++; p[fy] = fx; } } }

int main(void){ cin >> a >> b >> p1; for(int i = a; i <= b; i++) p[i] = i; for(int i = a; i <= b; i++){ for(int j = i+1; j <= b; j++){ if(i == j) continue; join(i, j); } } cout << sum << endl; return 0;