【题解】P10426

P10426（洛谷题面）

题目

题目描述：

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

$$S = H_a H_b H_c \cdot \frac{\operatorname{LCM}(H_a, H_b, H_c)}{\operatorname{LCM}(H_a, H_b) \cdot\operatorname{LCM}(H_a, H_c) \operatorname{LCM}(H_b, H_c)}$$

其中 $\operatorname{LCM}$ 表示的是最小公倍数函数。

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

输入格式：

第一行一个整数 $n$ 表示宝石个数。
第二行有 $n$ 个整数 $H_1, H_2, \dots H_n$ 表示每个宝石的闪亮度。

输出格式：

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

数据范围与说明：

数据规模与约定

• 对 $30\%$ 的数据，$n \leq 100$，$H_i \leq 10^3$。
• 对 $60\%$ 的数据，$n \leq 2 \times 10^3$。
• 对全部的测试数据，保证 $3 \leq n \leq 10^5$，$1 \leq H_i \leq 10^5$。

输入输出样例 #1

输入：

5
1 2 3 4 9

输出：

1 2 3

题意

简述：

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

$$S = H_a H_b H_c \cdot \frac{\operatorname{LCM}(H_a, H_b, H_c)}{\operatorname{LCM}(H_a, H_b) \cdot\operatorname{LCM}(H_a, H_c) \operatorname{LCM}(H_b, H_c)}$$

其中 $\operatorname{LCM}$ 表示的是最小公倍数函数。

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

代码

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],cnt[N];

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int lcm(int a,int b){
    return a*b/gcd(a,b);
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=1;j<=sqrt(a[i]);j++){
            if(a[i]%j==0){
                cnt[j]++;
                if(j!=sqrt(a[i]))   cnt[a[i]/j]++;
            }
        }
    }
    int x=1;
    for(int i=N-10;i>=1;i--){
        if(cnt[i]>=3){
            x=i;
            break;
        }
    }
    sort(a+1,a+n+1);
    
    int c=0;
    for(int i=1;i<=n;i++){
        if(a[i]%x==0){
            cout<<a[i]<<" ";
            c++;
            if(c==3)    return 0;
        }
    }
    return 0;
}