---

B. Divisors of Two Integers

原创 于 2023-08-28 22:06:26 发布 · 粉丝可见 · 158 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132549150

题目：

样例：

cobol<br/>10<br/>10 2 8 1 2 4 1 20 4 5<br/>

20 8

题意：

给出 一个列表数组，这个列表数组中，是两个正整数 x 和 y 的约数将它们放在了一块，请找出这两个 x 和 y 的值分别是多少。

解题思路：

这道题很有意思，就单纯的思维题。

从给的样例我们可以知道，一定有一个最大的数作为 x 或者 y，所以我们把 这个最大的约数弄出来之后，再把剩下的数中的最大数一定就是  y 或者 x。

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

umap<int, int>r;	// 统计我们这个数组各个元素出现的个数
int n, x, y;

inline void solve()
{
	cin >> n;
	for (int i = 0, value; i < n; ++i)
	{
		cin >> value;

		r[value]++; // 统计元素

		x = max(x, value);	// 找出 x
	}

	// 找出 x 的约数
	// 并删除掉我们出现过的该约数对应的 数值
	int tem = x;
	for (int i = 1; i * i <= tem; ++i)
	{
		if (tem % i == 0)
		{
			r[i]--;
			if (i * i != tem)
			{
				r[tem / i]--;
			}
		}
	}

	// 由于我们的 数据范围 是 1e4 所以直接暴力即可
	for (int i = 0; i <= 1e4; ++i)
	{
		if (r[i])
		{
			y = i;
		}
	}
	cout << x << ' ' << y << endl;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：