Codeforces 1154G 枚举

发布时间：2020-12-14 04:33:11 所属栏目：大数据来源：网络整理

导读：题意：给你一堆数，问其中lcm最小的一对数是什么？思路：因为lcm(a,b) = a * b / gcd(a,b),所以我们可以考虑暴力枚举gcd，然后只找最小的a和b，去更新答案即可。数据范围1e7? 不慌，bitset搞一下， 1e7log(1e7)可以500ms过。代码： #include bits/stdc++

题意：给你一堆数，问其中lcm最小的一对数是什么？

思路：因为lcm(a,b) = a * b / gcd(a,b),所以我们可以考虑暴力枚举gcd，然后只找最小的a和b，去更新答案即可。

数据范围1e7? 不慌，bitset搞一下， 1e7log(1e7)可以500ms过。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
bitset<maxn * 10> v,v1;
int a[maxn];
vector<int> ans;
long long res = 1e18;
int main() {
	int n,res1,res2,pos1 = -1,pos2 = -1,mx = 0;
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) {
		scanf("%d",&a[i]);
		mx = max(mx,a[i]);
		if(v[a[i]] == 1) v1[a[i]] = 1;
		v[a[i]] = 1;
	}
	for (int i = 1; i <= mx; i++) {
		ans.clear();
		for (int j = i; j <= mx; j += i) {
			if(v[j]) {
				ans.push_back(j);
				if(v1[j]) ans.push_back(j);
				if(ans.size() >= 2) break;
			}
		}
		if(ans.size() < 2) continue;
		if(res > (long long)ans[0] * ans[1] / i) {
			res = (long long)ans[0] * ans[1] / i;
			res1 = ans[0],res2 = ans[1];
		}
	}
	int flag = 0;
	for (int i = 1; i <= n; i++) {
		if(pos1 == -1 && res1 == a[i]) {
			pos1 = i;
			flag |= 1;
			continue;
		}
		if(pos2 == -1 && res2 == a[i]) {
			pos2 = i;
			flag |= 2;
		}
		if(flag == 3) break;
	}
	if(pos1 > pos2) swap(pos1,pos2);
	printf("%d %dn",pos1,pos2);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!