51nod 1179：最大的最大公约数

1179 最大的最大公约数

题目来源： SGU

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

关注

给出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示例

Output示例

从数组中最大的数开始试验，看其倍数是否满足出现了两次的要求，出现了两次，还是从最大的数开始递减的话，说明这个数一定是这些数中的最大的最大公约数。

代码：

#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;

}

巴特西

51nod 1179：最大的最大公约数

最新文章

热门文章