整数合并

Solution

对于有相同质因数的数字加入一个集合，最后统计集合的个数即可（爸爸是自己的点的个数）

Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <vector>
#include <queue>
#define L 100010
#define LL long long
using namespace std;
int a, b, p, prim[L], cnt, f[L], ans;
bool check[L];
inline int find(int x) { return (f[x] == x) ? x : f[x] = find(f[x]);}
inline void makeset(int x, int fa) {f[find(x)] = f[find(fa)];}
int main() {
freopen("CJOJ1504.in", "r", stdin);
freopen("CJOJ1504.out", "w", stdout);
scanf("%d %d %d", &a, &b, &p);
for (int i = a; i <= b; ++i) f[i] = i;
for (int i = 2; i <= b; ++i) {
if (!check[i]) prim[++cnt] = i;
for (int j = 1; j <= cnt && i * prim[j] <= b; ++j) {
check[prim[j] * i] = 1;
if (i % prim[j] == 0) break;
}
}
for (int i = 1; i <= cnt; ++i)
if (prim[i] >= p) {
int c = a / prim[i] * prim[i];
if (c != a) c += prim[i];
for (int j = c + prim[i]; j <= b; j += prim[i]) makeset(j, c);
}
for (int i = a; i <= b; ++i) if (f[i] == i) ans++;
printf("%dn", ans);
return 0;
}

Summary

注意合并集合的时候试讲他们的父亲放在一起，以及初始化的时候初始自己的父亲是自己

最后

以上就是诚心店员为你收集整理的CJOJ 1504 整数合并DescriptionInputOutputSample InputSample OutputHintSourceSolutionCodeSummary的全部内容，希望文章能够帮你解决CJOJ 1504 整数合并DescriptionInputOutputSample InputSample OutputHintSourceSolutionCodeSummary所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。