This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Practice makes perfect
#include <bits/stdc++.h>
#include <set>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
#define file ""
#define ll long long
const int maxn = 1e5 + 5;
int n, p[maxn], lab[maxn];
set<int> s;
ll ans = 0;
struct Edge {
int u, v, w;
bool operator < (Edge &e) {
return w < e.w;
}
};
vector<Edge> edges;
int Find(int u) {
return lab[u] < 0 ? u : lab[u] = Find(lab[u]);
}
bool unite(int a, int b) {
a = Find(a);
b = Find(b);
if (a == b)
return 0;
if (lab[a] > lab[b])
swap(a, b);
lab[a] += lab[b];
lab[b] = a;
return 1;
}
int main() {
fastIO
//freopen(file".inp", "r", stdin);
//freopen(file".out", "w", stdout);
cin >> n;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
s.insert(x);
}
vector<int> v = vector<int>(s.begin(), s.end());
if (v[0] == 1 || v.size() == 1) {
cout << 0;
return 0;
}
for (int i = 0; i < n; ++i)
lab[i] = -1;
n = v.size();
int mx = v[n - 1];
for (int i = 0; i < n; ++i) {
int j = i;
for (int val = v[i]; val <= mx; val += v[i]) {
int last = j;
while (j + 1 < n && v[j] < val)
j++;
if (v[j] == v[i])
j++;
if (j != n && last != j) {
Edge e;
e.u = i;
e.v = j;
e.w = v[j] % v[i];
edges.push_back(e);
}
}
}
sort(edges.begin(), edges.end());
for (Edge &e : edges)
if (unite(e.u, e.v))
ans += e.w;
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |