宝石组合 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100000 + 100;
int n, g;
int num[maxn], cnt[maxn];
vector<int> fac[maxn];
vector<int> ans;

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    for (int i = 1; i < maxn; ++i) {
        for (int j = i; j < maxn; j += i) {
            fac[j].push_back(i);
        }
    }
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        for (int j = 0; j < fac[num[i]].size(); ++j) {
            ++cnt[fac[num[i]][j]];
        }
    }
    for (int i = 1; i < maxn; ++i) {
        if (cnt[i] >= 3) {
            g = i;
        }
    }
    sort(num, num + n);
    for (int i = 0; i < n; ++i) {
        if (num[i] % g == 0) {
            ans.push_back(num[i]);
        }
    }
    for (int i = 0; i < 3; ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}