2019年四月四日D题

时间:2021-12-24 14:03:55

2019年四月四日D题

2019年四月四日D题

2019年四月四日D题

 

题意:

第一行输入代表下面输入的测试数对的个数

 

接下来的每个数对中 两个数中可以任意选择一个作为判断数字 选完n个之后 这些数对的最小公因数即为答案

换言之第一组选18 15 12得3,也可以选18 24 12得6或3或2 输出一个答案即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

ll A[1000000];
ll B[1000000];



int main () {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	ll ans = 0;
	ll x, y;
	for (int i = 0; i < n; ++i) {
		cin >> x >> y;
		A[i] = x;	B[i] = y;
		ans = __gcd(ans, x * y);	// 记录乘起来的最大公约数 这个数一定大于等于输入的数 并且答案一定是这个的最小的除了1的因数
	}
	if (ans == 1) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 0; i < n; ++i) {
		if (__gcd(A[i], ans) > 1) {  // 找出存在的更小的因子
			ans = __gcd(A[i], ans);
		}
		else
			ans = __gcd(B[i], ans);
	}
	cout << ans << endl;
}