B-Random

一、输入输出描述如图所示

二、核心思路

因为输入数据最大不超过1e9,sqrt(1e9)≈31622.78，所以可先使用欧拉筛，将所有不超过32000的质数记录进prime数组中。然后遍历每组输入数据，将每个数据分解质因数，并用map开一个数组，记录所出现过的质因子，一旦同一个质因子出现两次，则这两个数的必有两数的最大公约数是大于1，此时输出两数并结束循环，同时记录特殊情况：因为再对每个数分解质因数时，只分解了所有<=sqrt(x)的数，所以如果分解后的结果是大于1的，则也需将其记录map数组中。

三、代码

```#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M = 32000;
int prime[M] = {0};
bool vis[M];
void isPrime() {
	for (int i = 2; i <= M; i++) {
		if (!vis[i]) {
			prime[++prime[0]] = i;
		}
		for (int j = 1; j <= prime[0] && prime[j]*i <= M; j++) {
			vis[prime[j]*i] = true;
			if (i % prime[j] == 0)
				break;
		}
	}
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	isPrime();
	while (T--) {
		int n;
		cin >> n;
		vector<int> a(n + 2, 0);
		map<int, int> mp;
		int f = 0, f_o = 0;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			if (f)
				continue;
			int t = a[i];
			if (t % 2 == 0 && f_o) {
				cout << a[f_o] << " " << t << "\n";
				f = 1;
			} else if (t % 2 == 0) {
				f_o = i;
				mp[2] = i;
			}
			if (f == 0 ) {
				for (int k = 1; k <= prime[0] && prime[k]*prime[k] <= t; k++) {
					if (t % prime[k] == 0) {
						if (mp[prime[k]] && mp[prime[k]] != i) {
							cout << a[mp[prime[k]]] << " " << a[i] << "\n";
							f = 1;
							break;
						} else if (mp[prime[k]] == 0)
							mp[prime[k]] = i;
						while (t % prime[k] == 0) {
							t /= prime[k];
						}
					}
				}
			}
			if (f == 0 && t != 1) {
				if (mp[t] && mp[t] != i) {
					cout << a[mp[t]] << " " << a[i]<<endl;
					f = 1;
				} else {
						mp[t] = i;
				}
			}
		}
		if (f == 0)
			cout << -1 << "\n";
	}
	return 0;
}