#include #include using namespace std; using namespace atcoder; int main() { const int MX = 100000; vector> L(MX + 1); for (int i = 1; i <= MX; ++i) { int x = i; while (x < MX) { L[x].push_back(i); x += i; } } int N; cin >> N; vector A(N); for (int i = 0; i < N; ++i) cin >> A[i]; unordered_map>> D; vector> Mvec; for (int i = 0; i < N; ++i) { for (int p : L[A[i]]) { D[p].emplace_back(A[i], i); } } for (auto &[key, vec] : D) { sort(vec.begin(), vec.end()); for (int i = 1; i < vec.size(); ++i) { long long cost = 1LL * vec[0].first * vec[i].first / key; Mvec.emplace_back(cost, vec[0].second, vec[i].second); } } sort(Mvec.begin(), Mvec.end()); dsu DS(N); long long ans = 0; for (auto &[cost, i, j] : Mvec) { if (!DS.same(i, j)) { DS.merge(i, j); ans += cost; } } cout << ans << '\n'; return 0; }