#include #include #include using namespace std; struct UF { int gnum; vector par, rank, size; UF(int n) : par(n + 5), rank(n + 5), size(n + 5, 1), gnum(n) {for (int i = 0; i <= n; ++i) par[i] = i;} int root(int x) {return par[x] == x ? x : (par[x] = root(par[x]));} void unite(int x, int y) { x = root(x); y = root(y); if (x == y) return; --gnum; if (rank[x] < rank[y]) swap(x, y); par[y] = x; if (rank[x] == rank[y]) ++rank[x]; size[x] += size[y]; } int issame(int x, int y) {return root(x) == root(y);} int siz(int x) {return size[root(x)];} int gsiz() {return gnum;} }; int main() { const int b = 2e5; int n; cin >> n; vector a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector cnt(b + 1); for (int i = 0; i < n; ++i) ++cnt[a[i]]; long long ans = 0; for (int i = 0; i <= b; ++i) { long long tmp = max(0LL, cnt[i] - 1LL) * i; ans += tmp; if (cnt[i] > 1) cnt[i] = 1; } vector>> e; for (int i = 1; i <= b; ++i) { long long tmp = -1; for (int j = i; j <= b; j += i) { if (cnt[j]) { if (tmp == -1) tmp = j; else e.push_back({tmp * j / i, {tmp, j}}); } } } sort(e.begin(), e.end()); UF uf(b + 1); for (auto [w, uv] : e) { auto [u, v] = uv; if (uf.issame(u, v)) continue; ans += w; uf.unite(u, v); } cout << ans << endl; }