56 lines
1.4 KiB
C++
56 lines
1.4 KiB
C++
// lanqiao 19711 宝石组合
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
/*
|
||
解析:
|
||
唯一分解定理:
|
||
任何一个大于1的自然数N，如果N不是质数，那么N可以唯一分解成有限个质数的乘积
|
||
N1 = p1^a1*p2^a2*...*pn^an
|
||
N2 = p1^b1*p2^b2*...*pn^bn
|
||
则gcd(N1, N2)=p1^min(a1, b1)*p2^min(a2, b2)*... *pn^min(an, bn)
|
||
则lcm(N1, N2)=p1^max(a1, b1)*p2^max(a2, b2)*...*pn^max(an, bn)
|
||
假设Ha,Hb，Hc相同质因子的幂次分别为x,y,z则题目中的表达式等价于
|
||
x+y+z+max(x,y,z)-max(x,y)-max(x,z)-max(y,z)
|
||
*/
|
||
const int N = 1e5 + 10;
|
||
int a[N];
|
||
vector<int> fac[N], s[N];
|
||
int main() {
|
||
for(int i = 1; i <= 1e5; i++){
|
||
for(int j = i; j <= 1e5; j += i){
|
||
fac[j].push_back(i);
|
||
}
|
||
}
|
||
int n; cin>>n;
|
||
for(int i = 1; i<=n; i++) cin >> a[i];
|
||
// 保证字典序最小
|
||
sort(a+1, a+1+n);
|
||
for(int i = 1; i <=n; i++){
|
||
for(int j = 0; j < fac[a[i]].size(); j++){
|
||
s[fac[a[i]][j]].push_back(a[i]);
|
||
}
|
||
}
|
||
for(int i = 1e5; i>=0; i--){
|
||
if(s[i].size() >= 3){
|
||
cout << s[i][0] << " " << s[i][1] << " " << s[i][2] << endl;
|
||
break;
|
||
}
|
||
}
|
||
return 0;
|
||
}
|
||
/* test samples -> 1 2 3
|
||
5
|
||
1 2 3 4 9
|
||
*/
|
||
|
||
/*
|
||
排序后的宝石为 [1, 2, 3, 4, 9]。
|
||
因数数组 fac 和宝石数组 s 的关系如下：
|
||
s[1] 包含所有宝石 [1, 2, 3, 4, 9]。
|
||
s[2] 包含 [2, 4]。
|
||
s[3] 包含 [3, 9]。
|
||
s[4] 包含 [4]。
|
||
s[9] 包含 [9]。
|
||
最终，s[1] 中有5个宝石，满足条件。
|
||
输出前三个宝石: 1 2 3。
|
||
*/ |