Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.4 kB
2
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "codes/debug.h"
#else
#define debug(x...)
#endif

using ll = long long;
using ull = unsigned long long;
using db = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<db, db>;
using tiii = tuple<int, int, int>;
using str = string;

#define vt vector
#define pb push_back
#define eb emplace_back
#define ins insert
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

constexpr int maxA = 1e6 + 1;

void solve() {
    int n;
    cin >> n;
    vt<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vt<int> cnt1(maxA), cnt2(maxA);
    set<int> st;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                cnt2[j]++;
                if (j * j != a[i]) {
                    cnt2[a[i] / j]++;
                }
            }
        }
    }
    for (int j = 1; j * j <= a[0]; j++) {
        if (a[0] % j == 0) {
            cnt1[j]++;
            if (cnt2[j]) st.pb(j);
            if (j * j != a[0]) {
                cnt1[a[0] / j]++;
                if (cnt2[a[0] / j]) st.pb(a[0] / j);
            }
        }
    }
    ll ans = 0;
    while (!st.empty()) {
        int cur = *st.end();
        ans += cur;
        cnt2[cur]--;
        if (cnt2[cur] == 0) {
            st.erase(st.end()); // ??
        } else {
            /*
                теперь нам надо перенести все делители числа, которое мы подключили в наше
                дерево в левую часть (cnt1), и обновить cnt2 и set
                надо хранить для каждого делителя его владельца? 
                у нас тогда размер вектора будет в худшем случае 2 * sqrt(maxA) * n
            */
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}