| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1211783 | Madhav_1608 | Sirni (COCI17_sirni) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <stdio.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
#define double long double
#define F first
#define S second
const double eps = 1e-12;
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
FOR(i,0,v.size()){cout << v[i] << " ";}
cout << "\n";
}
ll gcd(ll a,ll b){
if(a==0){return b;}
else if(b==0){return a;}
else if(a<b){return gcd(b%a,a);}
else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
return (a/gcd(a,b))*b;
}
void setIO(string name = "") {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
void init_code(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
class DSU {
private:
vector<int> parents;
vector<int> sizes;
public:
DSU(int size) : parents(size), sizes(size, 1) {
for (int i = 0; i < size; i++) { parents[i] = i; }
}
/** @return the "representative" node in x's component */
int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
/** @return whether the merge changed connectivity */
bool unite(int x, int y) {
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root) { return false; }
if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
sizes[x_root] += sizes[y_root];
parents[y_root] = x_root;
return true;
}
/** @return whether x and y are in the same connected component */
bool connected(int x, int y) { return find(x) == find(y); }
};
void solve(){
// store very big numbers may mean log2
ll n;
cin >> n;
vll a(n);
FOR(i,0,n) cin >> a[i];
sort(all(a));
vll b;
b.push_back(a[0]);
FOR(i,1,n){
if(a[i]==a[i-1]) continue;
b.push_back(a[i]);
}
n = b.size();
vector<vll> edges;
FOR(i,0,n){
for(ll j=2ll*b[i];j<=b.back();j+=b[i]){
auto it = (lower_bound(all(b),j)-b.begin());
edges.push_back({b[it]-j,i,it});
}
auto it = upper_bound(all(b),b[i]);
if(it==b.end()) continue;
ll it1 = (it-b.begin());
edges.push_back({b[it1]-j,i,it1});
}
DSU dsu(n);
sort(all(edges));
ll ans = 0;
for(vll &v:edges){
if(dsu.connected(v[1],v[2])) continue;
ans += v[0];
dsu.unite(v[1],v[2]);
}
cout << ans << "\n";
}
signed main(){
//setIO
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// init_code();
ll t=1;
// cin >> t;
while(t--){
solve();
}
return 0;
}