#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 idx[(int)1e7+10];
int number[(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);
}
int ctr = 0;
for (int num : nums) {
idx[num] = ctr++;
}
for (int i = 0; i < n; i++) {
sz[i] = 1;
pa[i] = i;
}
auto it = nums.begin();
for (int i = 0; i <= 1e7; i++) {
while (it != nums.end() && *it < i) it++;
if (it == nums.end()) number[i] = -1;
else number[i] = *it;
}
for (int num : nums) {
int prev = -1;
for (int i = num; i <= 1e7; i += num) {
int it = i == num ? number[i+1] : number[i];
if (it != -1) {
if (prev == it) continue;
prev = it;
edges[it%num].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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
236 ms |
278324 KB |
Output is correct |
2 |
Correct |
270 ms |
279020 KB |
Output is correct |
3 |
Correct |
220 ms |
278636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
229 ms |
274540 KB |
Output is correct |
2 |
Correct |
548 ms |
275564 KB |
Output is correct |
3 |
Correct |
251 ms |
278636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
218 ms |
278508 KB |
Output is correct |
2 |
Correct |
217 ms |
276836 KB |
Output is correct |
3 |
Correct |
238 ms |
278668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
362 ms |
293028 KB |
Output is correct |
2 |
Correct |
565 ms |
319808 KB |
Output is correct |
3 |
Correct |
358 ms |
297300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
251 ms |
280684 KB |
Output is correct |
2 |
Correct |
372 ms |
300652 KB |
Output is correct |
3 |
Correct |
351 ms |
290600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
419 ms |
305028 KB |
Output is correct |
2 |
Correct |
538 ms |
334836 KB |
Output is correct |
3 |
Correct |
373 ms |
296400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
258 ms |
280400 KB |
Output is correct |
2 |
Correct |
509 ms |
328656 KB |
Output is correct |
3 |
Correct |
361 ms |
295516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
414 ms |
330988 KB |
Output is correct |
2 |
Correct |
1688 ms |
527244 KB |
Output is correct |
3 |
Correct |
430 ms |
333416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
415 ms |
330688 KB |
Output is correct |
2 |
Correct |
2430 ms |
616112 KB |
Output is correct |
3 |
Correct |
474 ms |
336864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
260 ms |
311788 KB |
Output is correct |
2 |
Correct |
2394 ms |
604496 KB |
Output is correct |
3 |
Correct |
364 ms |
297436 KB |
Output is correct |