蓝桥杯宝石组合（数论，因数）

 

输入样例：
5
1 2 3 4 9
输出样例：
1 2 3

 

思路：

如果直接按题意暴力的话，只能过30%，所以应该推导出更简便的公式，推导如下

或者多带几组数据会发现 S与三个数的最大公因数程正比，所以只要在这组数中找到3个数的最大公因数是所有组合里最大的即可，但是如果直接3个for循环分别找公因数会超时，所以我们干脆对每个数都找到它的因数，（因数最大也就是Hi最大为1e5）开vector二维数组，其中v[i][j]表示当因数为i时的第j+1个数，最后由于要找最大因数，我们倒叙输出即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,a[N];
vector<int> v[N];
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);for(int i=0;i<n;i++){for(int j=1;j*j<=a[i];j++){if(a[i]%j==0) {v[j].push_back(a[i]);if(a[i]/j!=j) v[a[i]/j].push_back(a[i]);}}}for(int i=1e5;i>=1;i--){if(v[i].size()>=3){cout<<v[i][0]<<" "<<v[i][1]<<" "<<v[i][2]<<endl;break;}}return 0;
}