菜鸡_如我
2019-08-25 21:27 复旦大学 C++
关注
#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
相关推荐
投递华为等公司10个岗位 > 
饿了么
| 校招
| 超多精选岗位
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
263931次浏览 2185人参与
# 0offer是寒冬太冷还是我太菜 #
887437次浏览 7909人参与
# 北方华创开奖 #
23664次浏览 260人参与
# 地方国企笔面经互助 #
2846次浏览 7人参与
# 学历or实习经历，哪个更重要 #
43438次浏览 328人参与
# 选完offer后，你后悔学本专业吗 #
13262次浏览 94人参与
# 查收我的offer竞争力报告 #
19522次浏览 255人参与
# 应届生被毁约被毁意向了怎么办 #
28203次浏览 243人参与
# 你最想要的公司福利是？ #
41869次浏览 146人参与
# 如何一边实习一边秋招 #
987380次浏览 12609人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3305次浏览 36人参与
# 嵌入式转岗的难度怎么样 #
11200次浏览 251人参与
# 你最希望上岸的公司是？ #
76542次浏览 469人参与
# 如何写一份好简历 #
605045次浏览 8510人参与
# 面试体验感最好的是哪家？ #
83651次浏览 818人参与
# 机械应届生薪资要多少才合适？ #
12542次浏览 61人参与
# 牛客十周岁生日快乐 #
48748次浏览 759人参与
# 你认为第一份工作重要吗 #
5447次浏览 49人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
79945次浏览 589人参与
# 秋招OC许愿 #
228209次浏览 1880人参与
# 来聊聊机械薪资天花板是哪家 #
65737次浏览 445人参与