第十五届蓝桥杯之宝石组合

这道题找精美程度最高的三个组合，根据我们数论的知识，也就是说找最大公因数最大的三个数

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int n;
int s[N];
vector<int> d[N];//开个桶
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i];
	}//输入闪亮值
	sort(s + 1, s + 1 + n);//给闪亮值排序，因为我们要按字典序最小输出
	for (int i = 1; i <= n; i++)//遍历每个闪亮度
	{
		for (int j = 1; j <= sqrt(s[i]); j++)//遍历1到根号下这个闪亮度，我们把闪亮度尾插到下标为因子的桶里面
		{
			if (s[i] % j == 0)
			{
				d[j].push_back(s[i]);//此时的j是1到根号s[i]的因子
				if (s[i] / j != j) d[s[i] / j].push_back(s[i]);//此时的s[i]/j就表示另一半因子
			}
		}
	}
	for (int i = N; i >= 1; i--)//闪亮度最高为N，我们从N一直往下找，直到找到因子对应三个闪亮度的因子，我们就把这三个闪亮度一次输出
 
	{
		if (d[i].size() >= 3)
		{
			for (int j = 0; j < 3; j++)
			{
				cout << d[i][j] << " ";
			}
			cout << endl;
			break;
		}
	}
 
 
 
	return 0;
}复制