#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
struct edge {
int u, v;
i64 w;
edge(int u = 0, int v = 0, i64 w = 0) : u(u), v(v), w(w) {}
};
const int MAXN = 1e7 + 5;
namespace dsu {
vector<int> lab;
void init(int N) {
lab.assign(N + 5, -1);
}
int root(int u) {
if(lab[u] < 0) return u;
return lab[u] = root(lab[u]);
}
bool is_same(int u, int v) {
return root(u) == root(v);
}
bool join(int u, int v) {
if(is_same(u, v)) return false;
u = root(u);
v = root(v);
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
}
int N;
int b[MAXN + 5];
vector<edge> edges;
signed main() {
#define task "code"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
vector<int> a(N + 1, 0);
for(int i = 1; i <= N; i++) cin >> a[i];
sort(a.begin() + 1, a.end());
dsu::init(N);
for(int i = 1; i <= N; i++) {
int j = i;
while(j < N and a[i] == a[j + 1]) {
dsu::join(i, j);
j++;
}
b[a[i]] = i;
i = j;
}
for(int i = a[; i >= 1; i--)
b[i] = (b[i] == 0 ? b[i + 1] : b[i]);
for(int i = 1; i <= N; i++) {
int j = i;
while(j < N and a[i] == a[j + 1]) {
dsu::join(i, j);
j++;
}
dsu::join(i, j);
if(b[a[i] + 1])
edges.emplace_back(i, b[a[i] + 1], a[b[a[i] + 1]] % a[i]);
for(int j = a[i]; j <= a[N]; j += a[i]) {
if(b[j])
edges.emplace_back(i, b[j], a[b[j]] % a[i]);
}
i = j;
}
sort(edges.begin(), edges.end(), [&](edge a, edge b) {
return a.w < b.w;
});
i64 ans = 0;
for(auto [u, v, w] : edges) {
if(dsu::join(u, v))
ans += w;
}
cout << ans;
return (0 ^ 0);
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:87:19: error: expected primary-expression before ';' token
87 | for(int i = a[; i >= 1; i--)
| ^
sirni.cpp:87:19: error: expected ']' before ';' token
87 | for(int i = a[; i >= 1; i--)
| ^
| ]
sirni.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
