#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ii pair<int, int>
int pa[100000], sz[100000];
vector<ii> edges[(int)1e7+10];
int findSet(int x) {
return pa[x] == x ? x : pa[x] = findSet(pa[x]);
}
void unite(int a, int b) {
a = findSet(a); b = findSet(b);
if (sz[a] > sz[b]) swap(a, b);
pa[a] = b;
sz[b] += sz[a];
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(false);
int n; cin >> n;
set<int> nums;
for (int i = 0; i < n; i++) {
int p; cin >> p;
nums.insert(p);
}
map<int, int> idx;
int ctr = 0;
for (int num : nums) {
idx[num] = ctr++;
}
for (int i = 0; i < n; i++) {
sz[i] = 1;
pa[i] = i;
}
for (int num : nums) {
int prev = -1;
for (int i = num; i <= 1e7; i += num) {
auto it = i == num ? nums.upper_bound(i) : nums.lower_bound(i);
if (it != nums.end()) {
if (prev == *it) continue;
prev = *it;
if (*it-i<num) edges[*it-i].emplace_back(idx[num], idx[*it]);
} else {
break;
}
}
/*
for (int num2 : nums) {
if (num < num2)
edges.pb(mp(num2%num, mp(idx[num], idx[num2])));
}
*/
}
ll ans = 0;
for (int c = 0; c <= 1e7; c++) {
for (auto e : edges[c]) {
if (findSet(e.f) != findSet(e.s)) {
ans += c;
unite(e.f, e.s);
}
}
}
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
168 ms |
235384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
171 ms |
235420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
175 ms |
235292 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
938 ms |
254076 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
218 ms |
237944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1942 ms |
265812 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
323 ms |
242028 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1070 ms |
256760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1072 ms |
256312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
252 ms |
239368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |