给出N个正整数，找出N个数两两之间最大公约数的最大值。例如：N = 4，4个数为：9 15 25 16，两两之间最大公约数的最大值是15同25的最大公约数5。
Input
第1行：一个数N，表示输入正整数的数量。(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应输入的正整数.(1 <= S[i] <= 1000000)
Output
输出两两之间最大公约数的最大值。
Input示例
4
9
15
25
16
Output示例
5
从数组中最大的数开始试验，看其倍数 是否满足出现了两次的要求，出现了两次，还是从最大的数开始递减的话，说明这个数一定是这些数中的最大的最大公约数。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; int n;
int val[50005];
int cnt[1000005]; int main()
{
//freopen("i.txt", "r", stdin);
//freopen("o.txt", "w", stdout); int i, j, maxn, sum;
scanf("%d", &n); maxn = 0;
for (i = 0; i < n; i++)
{
scanf("%d", val + i);
cnt[val[i]]++;
maxn = max(maxn, val[i]);
}
for (j = maxn; j >= 1; j--)
{
sum = 0;
for (i = j; i <= maxn; i = i + j)
{
sum += cnt[i];
if (sum >= 2)
{
break;
}
}
if (sum >= 2)
{
cout << j << endl;
break;
}
} //system("pause");
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。