#include <bits/stdc++.h>
using namespace std;
#define int long long
const int oo = 1e18;
const int MAXN = 1e5 + 7;
int par[MAXN];
int sz[MAXN];
int getl(int x)
{
if(par[x] == -1) return x;
return par[x] = getl(par[x]);
}
bool unite(int a, int b)
{
a = getl(a);
b = getl(b);
if(a == b) return false;
if(sz[a] > sz[b]) swap(a, b);
sz[b] += sz[a];
par[a] = b;
return true;
}
void _()
{
int n;
cin >> n;
vector<int>v(n);
for(int &i : v) cin >> i;
vector<array<int,3>>q;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
q.push_back({min(v[i] % v[j], v[j] % v[i]), i, j});
}
}
sort(q.begin(), q.end());
int sum = 0;
for(auto [w, u, v] : q)
{
if(unite(u, v))
{
sum += w;
}
}
cout << sum << endl;
}
signed main()
{
fill(par, par + MAXN, -1);
fill(sz, sz + MAXN, 1);
int tt = 1;
// cin >> tt;
while(tt--) _();
}
# | 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... |