公約數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;
}