题解：P10426 [蓝桥杯 2024 省 B] 宝石组合

· · 题解

题目分析

看到那么大长串的柿子不要慌

我们把式子 H _ {a} 看作圈 a ,把式子 H _ {b} 看作圈 b ,把式子 H _ {c} 看作圈 c

\begin{aligned} 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})}\\ &= (d \times h \times j \times g) \times (g \times j \times e \times i) \times (j \times i \times h \times f) \times\frac{(d \times e \times f \times g \times h \times i \times j)}{(d \times g \times h \times j \times i \times f) \times (d \times g \times h \times j \times e \times i) \times (h \times j \times i \times f \times g \times e)} \end{aligned}\\

化简完之后我们得到了

S=j\\ $$ S=\gcd(H _ {a},H _ {b},H _ {c}) $$ # 做题思路 1.找一个 $cnt[i]$ 用于记录从 $H _ {1}，H _ {2}$ 一直到 $H _ {n}$ 中能被 $i$ 整除的个数。 2.找到最大的 $i$ 使得 $cnt[i] \ge 3$ 记为 $x

3.从小到大排序 H 数组。
4.从 1 到 n 遍历，判断 H _ {i}\mid x ，输出前 3 个满足要求的数。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],cnt[N];
int main()
{
    int n,x,c=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        for(int j=1;j*j<=h[i];j++) {
            if(h[i]%j==0){
                cnt[j]++;
                if(j*j!=h[i]) cnt[h[i]/j]++; 
            }
        }
    }
    for(int i=N-5;i>=1;i--){
        if(cnt[i]>=3){
            x=i;
            break;
        }
    }
    sort(h+1,h+n+1);
    for(int i=1;i<=n;i++){
        if(h[i]%x==0){
            cout<<h[i]<<" ";
            c++;
        }
        if(c==3) return 0;
    }
    return 0;
}

完结撒花 点个赞趴