蓝桥杯刷题--宝石组合
在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 HiHi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度SS 可以用以下公式来衡量：
其中 LCM 表示的是最小公倍数函数。
小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。
输入格式
第一行包含一个整数 N 表示宝石个数。
第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。
输出格式
输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。
思路
- 统计每个闪亮度出现的次数，存到cnt中。
- 从大到小枚举最大的gcd。在cnt中找它的倍数，累加个数并添到ans数组中。当个数大于等于3时，直接输出ans的值。
- 注意ans数组创建的时机，是每枚举一个gcd然后创建一个ans。
for(int i = max_a;i >= 1;i--){int cnt = 0; vector<int> ans;for(int j = i;j <= max_a;j+=i){//}化简题目思路
p都是底数，a b c 是指数
- 设Ha=p1a1p2a2⋯pnan，Hb=p1b1p2b2⋯pnbn，Hc=p1c1p2c2⋯pncn（分解质因数形式）
根据最小公倍数的质因数求法：对于两个数m=p1x1p2x2⋯pnxn，n=p1y1p2y2⋯pnyn ，LCM(m,n)=p1max(x1,y1)p2max(x2,y2)⋯pnmax(xn,yn) 。- LCM(Ha,Hb)=p1max(a1,b1)p2max(a2,b2)⋯pnmax(an,bn) ；
- LCM(Ha,Hc)=p1max(a1,c1)p2max(a2,c2)⋯pnmax(an,cn) ；
- LCM(Hb,Hc)=p1max(b1,c1)p2max(b2,c2)⋯pnmax(bn,cn) ；
- LCM(Ha,Hb,Hc)=p1max(a1,b1,c1)p2max(a2,b2,c2)⋯pnmax(an,bn,cn) 。
- HaHbHc=p1a1+b1+c1p2a2+b2+c2⋯pnan+bn+cn 。
- 分析分子分母中质因数的指数关系
对于质因数pi ：- 分子中pi的指数为ai+bi+ci+max(ai,bi,ci) 。
- 分母中pi的指数为max(ai,bi)+max(ai,ci)+max(bi,ci) 。
通过分析指数大小关系（分多种情况讨论ai，bi，ci的大小顺序，如ai≥bi≥ci 时：分子指数为ai+bi+ci+ai，分母指数为ai+ai+bi ，相减得ci ；其他大小顺序情况类似分析 ），可以发现分子分母相除后，对于每个质因数pi ，化简后指数为gcd(ai,bi,ci)（gcd表示最大公约数）。 - 所以S=gcd(Ha,Hb,Hc) 。
最终答案
#include <iostream>
//#include <bits/stdc++.h>
#include <vector>
#include <unordered_map>
using namespace std;int main()
{// 请在此输入您的代码ios::sync_with_stdio(false);cin.tie(nullptr);int n; cin >> n;int mp[500100] = {0};int max_a = 0;for(int i = 0;i < n;i++){int a; cin >> a;mp[a]++;if(a > max_a) max_a = a;}for(int i = max_a;i >= 1;i--){int cnt = 0; vector<int> ans;for(int j = i;j <= max_a;j+=i){if(mp[j]){cnt += mp[j];for(int k = 0;k < mp[j] && ans.size() < 3;k++){ans.push_back(j);}if(cnt >= 3){for(int l = 0;l < 3;l++){cout << ans[l] << " ";}return 0;}}}}return 0;
}