在一個神秘的森林里，住著一個小精靈名叫小藍。有一天，他偶然發現了一個隱藏在樹洞里的寶藏，里面裝滿了閃爍著美麗光芒的寶石。這些寶石都有著不同的顏色和形狀，但最引人注目的是它們各自獨特的 “閃亮度” 屬性。每顆寶石都有一個與生俱來的特殊能力，可以發出不同強度的閃光。小藍共找到了?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?=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???。
- 分析分子分母中質因數的指數關系
對于質因數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;
}
ldconfig)
