宝石组合

先对公式进行化简，发现精美程度 S 等价于三数的最大公约数 gcd(Ha​,Hb​,Hc​)。因此，问题转化为找出能整除至少 3 个数的最大整数 x，然后找到最小的三个整除x的数

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,x,flag=0;
	cin>>n;
    vector<int>h(n+1);
    unordered_map<int,int>cnt;
	for(int i=1;i<=n;i++){
		cin>>h[i];
		for(int j=1;j<=sqrt(h[i]);j++) {
			if(h[i]%j==0){
				cnt[j]++;
				if(j*j!=h[i]) cnt[h[i]/j]++; 
			}
		}
	}
	// 从大到小查找，找到最大的能整除至少3个的数·
	for(int i=1e5;i>=1;i--){
		if(cnt[i]>=3){
			x=i;
			break;
		}
	}
	//输出最小的三个数
	 sort(h.begin() + 1, h.end());
	for(int i=1;i<=n;i++){
		if(h[i]%x==0){
			cout<<h[i]<<" ";
			flag++;
		}
		if(flag==3) return 0;
	}
	return 0;
}