关注
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0)return a;
else return gcd(b, a%b);
}
int flag[1000];
int getFather(int x) {
if (flag[x] == -1)return x;
else {
int tmp = getFather(flag[x]);
flag[x] = tmp;
return tmp;
}
}
int main() {
int n;
cin >> n;
vector<int>sugar(n);
vector<int>nums(n);
for (int i = 0; i < n; i++) {
cin >> sugar[i];
flag[i] = -1;
nums[i] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (gcd(sugar[i], sugar[j]) > 1) {
int a = getFather(i);
int b = getFather(j);
if (a != b) {
flag[a] = b;
nums[b] += nums[a];
}
}
}
}
int res = 0;
for (int i = 0; i < n; i++)
res = max(res, nums[i]);
cout << res << endl;
return 0;
}
我用并查集做的,也是70%
查看原帖
点赞 2
相关推荐
走呀走:华子二面可能会有场景题的,是有些开放性的问题了
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# i人适合做什么工作 #
4875次浏览 61人参与
# 大家实习每天都在干啥 #
95579次浏览 533人参与
# 快手技术岗信息交流阵地 #
13944次浏览 80人参与
# 我是面试官,请用一句话让我破防 #
5783次浏览 52人参与
# 你认为哪些项目算烂大街? #
72742次浏览 606人参与
# 如果秋招能重来,我会____ #
21112次浏览 195人参与
# “vivo”个offer #
27811次浏览 203人参与
# 许愿池 #
320874次浏览 2905人参与
# 校招生月薪1W算什么水平 #
7594次浏览 53人参与
# 硬件应届生薪资是否普遍偏低? #
88064次浏览 559人参与
# 华为池子有多大 #
105274次浏览 740人参与
# 苦尽甘来时,再讲来时路 #
20089次浏览 306人参与
# 作业帮求职进展汇总 #
70436次浏览 484人参与
# 如果上班像打游戏,你最想解锁什么技能 #
3940次浏览 43人参与
# 一份好的简历长什么样? #
10377次浏览 241人参与
# 为了实习逃课值吗? #
16861次浏览 147人参与
# 你认为小厂实习有用吗? #
94769次浏览 609人参与
# 秋招许愿,本周能____ #
19927次浏览 135人参与
# 班味很重的人是啥样的? #
6013次浏览 39人参与
# 投递无反馈,如何优化求职策略? #
3400次浏览 32人参与
# 大学最后一个寒假,我想…… #
62219次浏览 668人参与
# 机械制造秋招总结 #
83994次浏览 826人参与
查看9道真题和解析