第十五届蓝桥杯之宝石组合
这道题找精美程度最高的三个组合，根据我们数论的知识，也就是说找最大公因数最大的三个数
#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;
}