蓝桥杯2024年第十五届省赛真题-宝石组合

思路：参考博客，对Ha,Hb,Hc分别进行质因数分解会发现，S实在就等于Ha，Hb，Hc的最大公约数，不严谨推导过程如下（字丑勿喷）：

找到此规律后，也不能枚举Ha，Hb，Hc，需要用桶排序，将1-10^5作为桶，把输入的数放到对应的因子桶中，从后往前第一个满意3个因子的数即为最大的S。时间复杂度最多是O(10的5次方*10的2.5次方+10的5次方）

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. #define endl '\n'
5. #define pp ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
6. const int N = 1e5+1;
7. vector<int>a[N];
8. int s[N];
9. int n;
10. void solve(){
11.     pp;
12.     cin>>n;
13.     for(int i=0;i<n;i++)cin>>s[i];
14.     sort(s,s+n);
15.     for(int i=0;i<n;i++){
16.         for(int j=1;j<=sqrt(s[i]);j++){
17.             if(s[i]%j==0){
18.                 a[j].push_back(s[i]);
19.                 //需要在满足是因子的基础上判断是否是乘方因子，放在外面是错的
20.                 if(s[i]/j!=j)a[s[i]/j].push_back(s[i]);
21.             }
22.         }
23.     }
25.     for(int i=N-1;i>=0;i--){
26.         if(a[i].size()>=3){
27.             cout<<a[i][0];
28.             for(int j=1;j<3;j++)cout<<" "<<a[i][j];
29.             break;
30.         }
31.     }
32.     return ;
33. }
35. signed main( ){
36.     int T=1;
37.     while(T--)solve();
38.     return 0;
39. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。