题目中的S可以转化为求三个数的最大公因数。如果暴力枚举的话1e5的三次方是超过数据范围的。 可以考虑枚举S，从大到小去枚举。因为求的是三个数的最大公因数，可以反过来想去枚举答案的倍数中存不存在三个数。如果存在这三个数，那这三个数的最大公因数就是当前枚举的最优解S。 ``` #include <iostream> using namespace std; const int N = 1e5 + 5; int main() { int h[N] = {0}; int n; cin >> n; for (int i = 0; i < n; i++) //将闪亮度存起来 { int temp; cin >> temp; h[temp]++; } int ans[3]; for (int i = 1e5; i > 0; i--) //枚举答案，从1e5开始枚举 { int idx = 0; for (int j = i; j <= 1e5; j += i) //答案的倍数，看存不存在某个宝石的因数是答案 { if (h[j] && idx < 3) { for(int k = 0;k<h[j];k++) { ans[idx++] = j; } } if (idx >= 3) { for (int k = 0; k < 3; k++) { cout << ans[k] << " "; } return 0; } } } return 0; } ```

``` #include <bits/stdc++.h> using namespace std; // 获取一个数的所有因数（包含1和自身） vector<int> getDivisors(int x) { vector<int> divisors; // 遍历到平方根以优化因数查找效率 for (int i = 1; i * i <= x; ++i) { if (x % i == 0) { // 发现因数i divisors.push_back(i); if (i != x / i) { // 避免重复添加平方根的情况 divisors.push_back(x / i); // 对应的另一个因数 } } } return divisors; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int> H(n); // 读取所有宝石的闪亮度 for (int i = 0; i < n; ++i) { cin >> H[i]; } // 统计每个因数出现的次数（用于寻找最大公约数候选） unordered_map<int, int> cnt; // 遍历所有宝石 for (int x : H) { // 获取当前宝石的所有因数 vector<int> divisors = getDivisors(x); // 每个因数出现次数+1 for (int d : divisors) { cnt[d]++; } } // 收集所有可能的公约数候选 vector<int> uniqueD; for (const auto& kv : cnt) { uniqueD.push_back(kv.first); } // 将候选因数按降序排列，优先处理大的因数 sort(uniqueD.begin(), uniqueD.end(), greater<int>()); // 遍历所有候选因数 for (int d : uniqueD) { // 需要至少三个数包含这个因数 if (cnt[d] >= 3) { vector<int> candidates; // 收集所有能被d整除的宝石 for (int x : H) { if (x % d == 0) { candidates.push_back(x); } } // 需要至少三个候选才能形成组合 if (candidates.size() >= 3) { // 排序确保字典序最小 sort(candidates.begin(), candidates.end()); // 输出前三个最小的候选 cout << candidates[0] << " " << candidates[1] << " " << candidates[2] << '\n'; return 0; // 找到最优解后立即退出 } } } // 备用方案：当没有符合条件的因数时（理论上不会触发） vector<int> sortH = H; sort(sortH.begin(), sortH.end()); // 输出全局最小的三个数（字典序保证） cout << sortH[0] << " " << sortH[1] << " " << sortH[2] << '\n'; return 0; } ```