#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { if(n<0) return 0; return (n*(n+1))/2; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = 1e18;
struct DSU {
vll pa;
ll n, gr;
DSU (ll n): n(n), gr(n), pa(n+2, 0) { fo (i, n+2) pa[i] = i; }
ll find (ll i) { return pa[i] == i ? i : pa[i] = find(pa[i]); }
void unite (ll i, ll j) {
i = find(i);
j = find(j);
if (i == j) return;
if (i > j) swap(i, j);
gr--;
pa[j] = i;
}
};
void test_case () {
ll n;
cin >> n;
vll a(n);
fo (i, n) cin >> a[i];
sort(all(a));
a.erase(unique(all(a)), a.end());
n = sz(a);
ll mx = *max_element(all(a));
vll idx(mx+1, -1), vis(n+1, -1);
vector<vll> cmps;
fo (i, n) idx[a[i]] = i;
if (a[0] == 1 || n == 1) {
cout << "0\n";
return;
}
{DSU ok(n);
for (ll i = 1; i <= mx; i++) {
if (idx[i] == -1) continue;
for (ll j = 2*i; j <= mx; j += i) {
if (idx[j] == -1) continue;
ok.unite(idx[i], idx[j]);
}
}
ll id = 0;
fo (i, n) {
ll j = ok.find(i);
if (vis[j] == -1 ) vis[j] = id++, cmps.pb({});
cmps[vis[j]].pb(i);
}
}
ll ans = 0;
while (sz(cmps) > 1) {
vector<vector<pll>> prv(mx+2, vpll(2, mp(-1, -1))), nxt(mx+2, vpll(2, mp(-1, -1)));
vll st(mx+2, -1);
vector<array<ll, 2>> mul(mx+2, {-1, -1});
fo (c, sz(cmps)) {
for (ll i: cmps[c]) {
st[a[i]] = c;
for (ll j = a[i]; j <= mx; j += a[i]) {
if (mul[j][0] == -1) mul[j][0] = c;
else mul[j][1] = c;
}
}
}
fore (i, 1, mx+1) {
if (min(mul[i][0], mul[i][1]) > -1 && mul[i][0] != mul[i][1]) {
prv[i] = {{i, mul[i][0]}, {i, mul[i][1]}};
continue;
}
prv[i] = prv[i-1];
if (mul[i][0] == -1) continue;
prv[i][0] = {i, mul[i][0]};
if (mul[i][0] != prv[i-1][0].se) {
prv[i][1] = prv[i-1][0];
}
}
forex (i, mx+1, 1) {
nxt[i] = nxt[i+1];
if (st[i] == -1) continue;
nxt[i][0] = {i, st[i]};
if (st[i] != nxt[i+1][0].se)
nxt[i][1] = nxt[i+1][0];
}
DSU ok(sz(cmps));
fo (c, sz(cmps)) {
array<ll, 2> bst = {INF, -1};
for (ll i: cmps[c]) {
for (ll j = a[i]; j <= mx; j += a[i]) {
pll p = {-1, -1};
if (nxt[j][0].se != c) p = nxt[j][0];
else p = nxt[j][1];
if (p == mp(-1ll, -1ll)) continue;
if (p.fi-j < bst[0])
bst = {p.fi-j, p.se};
}
pll p = {-1, -1};
if (prv[a[i]][0].se != c) p = prv[a[i]][0];
else p = prv[a[i]][1];
if (p == mp(-1ll, -1ll)) continue;
if (a[i]-p.fi < bst[0])
bst = {a[i]-p.fi, p.se};
}
if (bst[1] >= 0 && ok.find(c) != ok.find(bst[1])) {
ans += bst[0];
ok.unite(c, bst[1]);
}
}
if (ok.gr == 1) break;
vis = vll(sz(cmps), -1);
vector<vll> ncmps(ok.gr);
ll id = 0;
fo (c, sz(cmps)) {
ll nc = ok.find(c);
if (vis[nc] == -1 ) vis[nc] = id++;
for (ll i: cmps[c]) {
ncmps[vis[nc]].pb(i);
}
}
cmps = ncmps;
}
cout << ans << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
while (tt--) test_case();
}
# | 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... |