蓝桥杯刷题--宝石组合

在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 HiHi​，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度SS 可以用以下公式来衡量：

其中 LCM 表示的是最小公倍数函数。

小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。

输入格式

第一行包含一个整数 N 表示宝石个数。

第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。

输出格式

输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

思路

1. 统计每个闪亮度出现的次数，存到cnt中。
2. 从大到小枚举最大的gcd。在cnt中找它的倍数，累加个数并添到ans数组中。当个数大于等于3时，直接输出ans的值。
3. 注意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 是指数

---

1. 设Ha​=p1a1​​p2a2​​⋯pnan​​，Hb​=p1b1​​p2b2​​⋯pnbn​​，Hc​=p1c1​​p2c2​​⋯pncn​​（分解质因数形式）
   根据最小公倍数的质因数求法：对于两个数m=p1x1​​p2x2​​⋯pnxn​​，n=p1y1​​p2y2​​⋯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​)​ 。
   • Ha​Hb​Hc​=p1a1​+b1​+c1​​p2a2​+b2​+c2​​⋯pnan​+bn​+cn​​ 。
2. 分析分子分母中质因数的指数关系
   对于质因数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;
}