社区讨论
请问为什么介个代码会RE两个点呀
P1621集合参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m6q809gl
- 此快照首次捕获于
- 2025/02/04 16:31 去年
- 此快照最后确认于
- 2025/11/04 10:00 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int parent[N];
bool isComposite[N];
// 初始化并查集
void init(int n) {
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
}
// 查找并查集中x的根节点
int find(int x) {
if (x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
// 合并x和y所在的集合
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
// 埃拉托斯特尼筛法筛选素数
void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!isComposite[i]) {
for (int j = i * i; j <= n; j += i) {
isComposite[j] = true;
}
}
}
}
// 判断x和y是否有大于等于p的公共质因数
bool hasCommonFactor(int x, int y, int p) {
// 可以进一步优化为从质因数分解结果中查找
for (int i = min(x, y); i >= p; i--) {
if (!isComposite[i] && x % i == 0 && y % i == 0) {
return true;
}
}
return false;
}
int main() {
int a, b, p;
cin >> a >> b >> p;
init(b);
sieve(b);
for (int i = a; i < b; i++) {
for (int j = i + 1; j <= b; j++) {
if (hasCommonFactor(i, j, p)) {
unionSet(i, j);
}
}
}
int ans = 0;
for (int i = a; i <= b; i++) {
if (parent[i] == i) {
ans++;
}
}
cout << ans << endl;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...