Crystal Combination

Problem Statement

在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 $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$ 值升序排列后字典序最小的方案。

Input

第一行一个整数 $n$ 表示宝石个数。
第二行有 $n$ 个整数 $H_1, H_2, \dots H_n$ 表示每个宝石的闪亮度。

Output

输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

Sample Input

Sample Output

1

1 2 3

Constraints

对 $30%$ 的数据，$n \leq 100$，$H_i \leq 10^3$。
对 $60%$ 的数据，$n \leq 2 \times 10^3$。
对全部的测试数据，保证 $3 \leq n \leq 10^5$，$1 \leq H_i \leq 10^5$。

Solving

$$ gcd(H_{a},H_{b},H_{c})_{max} $$

故我们要在所有的宝石中找出三个宝石，使得这三个宝石的最大公因数最大。

依据题意，我们可以读入所有宝石的闪亮度，然后对其进行升序排序，用O(N$\sqrt{N}$)的复杂度筛选出存在于所有宝石中的所有因数，将他们压入一个二维动态数组vector中，其中第一维为这个因数本身，第二维是这个因数代表的宝石闪亮度，因为已经提前升序排序，所以其中的第二维一定是按字典序升序排序。故我们只需要从大至小遍历所有因数，直至找到某一个因数的第二维大小>=3，接着输出前三项并break即可：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 0;
const int M = 0;
vector<int> v[100010];
void solve()
{
    int n;
    cin >> n;
    int arr[n+1];
    int Max = 0;
    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
        Max = max(Max,arr[i]);
    }
    sort(arr+1,arr+1+n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;(ll)j*j<=arr[i];j++)
        {
            if(arr[i]%j==0)
            {   
                v[j].push_back(arr[i]);
                //当j是arr[i]的因数时，arr[i]/j也是他的因数.但为了避免j*j==arr[i]的情况重复加入，需要一个特判：
                if(arr[i]/j!=j)
                v[arr[i]/j].push_back(arr[i]);
            }
        }
    }
    for(int i=Max;i>=1;i--)
    {
        if(v[i].size()>=3)
        {
            for(int j=0;j<3;j++)
            {
                cout << v[i][j] << (j==2?'\n':' ');
            }
            break;
        }
    } 
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;
#ifdef Single
    T = 1;
#else
    cin >> T;
#endif
    while(T--)
    {
        solve();
    }
    return 0;
}