問題描述

在一個神秘的森林里，住著一個小精靈名叫小藍。有一天，他偶然發現了一個隱藏在樹洞里的寶藏，里面裝滿了閃爍著美麗光芒的寶石。這些寶石都有著不同的顏色和形狀，但最引人注目的是它們各自獨特的 “閃亮度” 屬性。每顆寶石都有一個與生俱來的特殊能力，可以發出不同強度的閃光。小藍共找到了?N?枚寶石，第?i?枚寶石的 “閃亮度” 屬性值為?Hi?，小藍將會從這?N?枚寶石中選出三枚進行組合，組合之后的精美程度?S?可以用以下公式來衡量：

其中?LCM?表示的是最小公倍數函數。

小藍想要使得三枚寶石組合后的精美程度?S?盡可能的高，請你幫他找出精美程度最高的方案。如果存在多個方案?S?值相同，優先選擇按照?H?值升序排列后字典序最小的方案。

輸入格式

第一行包含一個整數?N?表示寶石個數。

第二行包含?N?個整數表示?N?個寶石的 “閃亮度”。

輸出格式

輸出一行包含三個整數表示滿足條件的三枚寶石的 “閃亮度”。

樣例輸入

5
1 2 3 4 9

樣例輸出

1 2 3

評測用例規模與約定

對于?30% 的評測用例：3≤N≤100,1≤Hi≤1000 。

對于?60%的評測用例：3≤N≤2000 。

對于?100% 的評測用例：3≤N≤,1≤Hi≤?。

1.化簡公式

①根據公式直接化簡：

②推導：

（下面Ha、Hb、Hc表示為H1、H2、H3）

將H1、H2、H3表示成數字相乘的形式，a為H1、H2、H3的最大公約數，b為H1、H2的最大公約數，c為H1、H3的最大公約數，d為H2、H3的最大公約數，efg是H1、H2、H3各自的一部分

H1=abce? ?H2=abdf? ?H3=acdg

S=*=a

最后的結果就是這三個數的最大公約數

25分代碼：（暴力）

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e5+10;
int n, a[N];
int max1;  //max 是標準庫 <algorithm> 中定義的一個函數模板
int ans[3];int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1; i<=n; ++i) cin>>a[i];for(int i=1; i<=n; ++i){for(int j=i+1; j<=n; ++j){for(int k=j+1; k<=n; ++k){if(i!=j && j!=k && i!=k){int temp = __gcd(a[i], __gcd(a[j], a[k]));if(temp > max1){ max1 = temp;ans[0]=a[i], ans[1]=a[j], ans[2]=a[k];}}}}}sort(ans, ans+3);cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2];return 0;
}