一、题目描述

原题链接

在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 $n$ 枚宝石，第 $i$ 枚宝石的 “闪亮度” 属性值为 $H_i$，小蓝将会从这 $n$ 枚宝石中选出三枚进行组合，组合之后的精美程度 $S$ 可以用以下公式来衡量：

$$
S = H_a H_b H_c \cdot \frac{\operatorname{LCM}(H_a, H_b, H_c)}{\operatorname{LCM}(H_a, H_b) \cdot\operatorname{LCM}(H_a, H_c) \operatorname{LCM}(H_b, H_c)}
$$

其中 $\operatorname{LCM}$ 表示的是最小公倍数函数。

小蓝想要使得三枚宝石组合后的精美程度 $S$ 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 $S$ 值相同，优先选择按照 $H$ 值升序排列后字典序最小的方案。

二、解题思路

  通过集合法以及容斥原理，可得 $LCM(a,b,c) = \frac{a·b·c·gcd(a,b,c)}{gcd(a,b)·gcd(a,c)·gcd(bc)}$，也可得 $LCM(a,b) = \frac{a·b}{gcd(a,b)}$，因此将两式变量更换并带入 $S$ 式中，化简后可得 $S = gcd(H_a,H_b,H_c)$，故本题等价为求解数组中任意三个数的最大公约数。

  然而通过数据范围我们发现直接两两求解时间复杂度不允许，考虑进行优化。我们根据定义可得所找的就是三个数中最大的公共因数，提取一个数的所有因数的复杂度为 $O(\sqrt n)$，处理 $n$ 个数所有因数的复杂度为 $O(n\sqrt n)$，因此我们令 $v[i]$ 数组为有哪些数包含因数 $i$，例如 $v[2]$ 可包含 $4、6、8$ 等等，在处理后我们只需要从大到小遍历所有因数，找到首个 $v[i]$ 的长度大于 $3$ 的数即为答案（意义为在给出的数组中有大于等于 $3$ 个数的其中一个因数为 $i$），其中包含的三个数的具体数值即为我们要找的答案，题目中要求字典序最小，故在此之前对数组进行排序即可。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 100010;

vector<int> v[N];
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    sort(a+1,a+1+n);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j * j <= a[i];j++){
            if(a[i] % j == 0){
                if(v[j].size() < 3){
                    v[j].push_back(a[i]);
                }

                if(j * j < a[i] && v[a[i]/j].size() < 3){
                    //每一个因数还会对应另一个因数，比如对于27，这里根据因数3即可找到因数9，故sqrt(n)复杂度即可处理所有因数
                    v[a[i]/j].push_back(a[i]);
                }
            }
        }
    }
    for(int i = 100000;i>=1;i--){
        if(v[i].size() == 3){
            cout << v[i][0] << " " << v[i][1] << " " << v[i][2] << endl;
            break;
        }
    }
    return 0;
}