蓝桥杯 第十五届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组宝石组合_第十五届蓝桥杯软件赛省赛c/c++b 组题解

//宝石组合
//若有错误，请大佬更正
//用质因数分解的方法可以求出s（闪亮度）就是三个数的最大公因数
//比如说   a=2^3*5^6   b=2^0*5*7   a和b的最大公因数为2^0*5^6 
//                                 a和b的最小公倍数为2^3*5^7
//所以只需要从n个数中选出3个数使这三个数的最大公因数最大即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
vector<ll>v[100005];//  v[i]里面存的是i的倍数  比如i==5  v[i]里面可以有5  10  15……
ll n,max1=-1;
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;//  x是每个宝石的闪亮度
		cin>>x;
		if(x>max1)max1=x;//max1记录最大的闪亮度，用于遍历
		int m=sqrt(x);
		//存x的因子
		for(int j=1;j<=m;j++){
			if(x%j==0){
				if(x/j!=j){
					v[j].push_back(x);
					v[x/j].push_back(x);
				}else v[j].push_back(x);
			}
		}
	}
	//倒序遍历，找最大的因子，这个因子最少是三个x的因子
	for(int i=max1;i>=1;i--){
		if(v[i].size()>=3){
			//因为题目中说有多种方案时要输出字典序最小的，所以我们用升序排序，
			//输出前三个就行
			sort(v[i].begin(),v[i].end());
			cout<<v[i][0]<<' '<<v[i][1]<<' '<<v[i][2];
			break;
		}
	}
	return 0;
}