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

解题思路:

https://zhuanlan.zhihu.com/p/692286717

参考代码:

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int a[N];
int n;
vector<int> vd[N];
vector<int> cnt[N];
int main() {
	scanf("%d",&n);
	for(int i=1; i<=100000; i++) {
		for(int j=i; j<=100000; j+=i) {
			vd[j].push_back(i);
		}
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=1; i<=n; i++) {
		for(auto d:vd[a[i]]) {
			cnt[d].push_back(a[i]);
		}
	}
	int res=0;
	for(int i=1; i<N; i++) {
		if(cnt[i].size()>=3) res=i;
	}
	for(int i=0; i<3; i++) {
		printf("%d ",cnt[res][i]);
	}
	return 0;
}