公约数1

公约数

【问题描述】

小 w 最近仔细研究了公约数，他想到了以下问题：

现有 n 个正整数，从中选 k（2<=k<=n）个，设这 k 个数的最大公约数为 g，则这 k 个数

的价值为 k*g。求这个价值的最大值。

小 w 当然知道答案了。现在他想考考你，你能很快回答出来吗？

【输入格式】

第一行，一个整数 n。

第二行，n 个正整数。

【输出格式】

一行一个正整数，表示答案。

【输入输出样例】

输入：

5

4 6 3 8 9

输出：

9

【数据范围】

对于 30%数据，N<=100

对于 100%数据，N<=200000，输入第二行每个数字不超过 2000000

分析：

又是两个因素限制结果，我们沿用往昔的思路，枚举一个，计算另一个。

这里，我们可以枚举最大公约数，然后计算有多少个数是其的倍数，取最大值即可。

参考程序：

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxm=2100000;
const int maxn=210000;
int a[maxn];
int n;
int b[maxm];
int main(){
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
		for (int j=1;j*j<=a[i];j++)
			if (a[i]%j==0){
				b[j]++;
				if (j*j!=a[i])b[a[i]/j]++;
			}
	int Max=*max_element(a+1,a+n+1);
	long long ans=0;
	for (int i=1;i<=Max;i++)
		if (b[i]>1)ans=max(ans,(long long)i*b[i]);
	printf("%lld\n",ans);
	return 0;
}