当前位置：首页 > news >正文

宝石组合（蓝桥杯）

news 2025/8/27 20:02:14

发现规律很重要，推荐这篇文章讲解<——————看这位大佬的讲解，很清楚

（在文末想和聪明的你讨论一个问题，盼望您的讨论与解答）

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int v[N];
vector<int>q;
int ksm(int a,int b)
{int ans=1;while(b){if(b&1)ans=ans*a;a=a*a;b>>=1;}return ans;
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int j;cin>>j;v[j]++;}for(int i=1e5;i>=1;i--){for(int j=i;j<=1e5;j+=i){if(v[j]){for(int t=1;t<=v[j];t++){q.push_back(j);if(q.size()==3)break;}}if(q.size()==3){for(int k=0;k<=2;k++){cout<<q[k]<<" ";}return 0;}}q.clear();}}

学习完这道题后，我在想，既然可以找出1e5数列中的任意三个数字的最大gcd（最小公倍数），

那么有没有可能在同样为 $O(n\sqrt{n})$ 的时间下，找出1e5数列中的任意三个数字的最小lcm（最大公因数），只需对称着写？
如下

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;const int N = 2e5 + 10;
int v[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){int x;cin >> x;v[x]++;}vector<int> best_ans;for (int i = 1; i <= 1e5; i++){vector<int> q;for (int j = 1; j <= sqrt(i); j++){if (i % j == 0){// 收集小因子j，最多3个if (v[j] > 0){for (int k = 1; k <= v[j] && q.size() < 3; k++){q.push_back(j);}}// 收集大因子i/j，最多3个if (j * j != i && v[i/j] > 0){for (int k = 1; k <= v[i/j] && q.size() < 3; k++){q.push_back(i/j);}}if (q.size() >= 3){sort(q.begin(), q.end());if (best_ans.empty() || q < best_ans){best_ans = q;}break;}}}}for (int t = 0; t < 3; t++){cout << best_ans[t] << " ";}return 0;
}

BUT！！！在一个数列里是否存在三个有公因数的组合，他们的最小公倍数大于三个互质数的最小公倍数，来使得我的code错误，但是我找不到这样的组合？？？

查看全文

http://www.xdnf.cn/news/1372879.html