题目链接:传送门

题意:

给你n对数, 每队数字有两个,问是否有一个数不等于1至少能整除每一对数中其中一个数字?

如果有,输出那个数,没有则输出-1,答案多个输出其中一个。

题解:能整除这个数的一定是该数的因子,而整除这对数其中一个数的一定是这对数两个数乘积的因子,那么我们可以把首项其中一个数与接下来每一项的乘积求gcd,得出来的结果不等于1则再去求其最小不为1因子。

AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<list>
#define ll long long
using namespace std;
ll fin(ll ans){
	for(int i = 2; i*i <= ans; i++){
		if(ans % i == 0){
			return i;
		}
	}
	return ans;
}
int main() {
	ll n, a, b;
	scanf("%lld%lld%lld",&n,&a,&b);
	ll x, y;
	for(int i = 1; i < n; i++){
		scanf("%lld%lld",&x,&y);
		a = __gcd(x*y,a);
		b = __gcd(x*y,b);
	}
	if(max(a,b) == 1){
		printf("-1\n");
	}else {
		printf("%lld\n",fin(max(a,b)));
	}
	return 0;
}