有 $n$ 组数对 $(a_i,b_i)$ ,求一个数使得 $\forall i,d|a_i\lor d|b_i$ 。
因为随便求所以找共有的素因子就好了,那么先求出 $GCD$ 表示所有 $lcm(a_i,b_i)$ 的 $gcd$ ,然后找 $GCD$ 的素因子。但 $GCD$ 有 $10^{18}$ 级别,上MR&PR就好啦!更简单的方法就是用 $GCD$ 去匹配 $a_i$ 或 $b_i$ ,如果 $(GCD,a_i)>1$ 就 $GCD=(GCD,a_i)$ 否则 $GCD=(GCD,b_i)$ 。
Miller-Rabin(MR)素数判断是利用费马小定理 $a^{p-1}\equiv1\ (mod\ p)$ 的逆定理:如果 $a^{p-1}\equiv1\ (mod\ p)$ 则 $p$ 是素数。
然而这货是伪命题,但有很大概率正确。所以我们可以随机几个 $a$ 来验证,如果 $a^{n-1}\not\equiv1\ (mod\ n)$ 则 $n$ 不是素数。但这样并不保险……有个二次探测定理:如果 $p$ 是素数,且 $x^2\equiv 1\ (mod\ p)$ 那么 $x=1\lor x=p-1$ ,这个移下项就出来了:$p|(x+1)(x-1)$ 。假如待测数是 $n$ ,我们把 $n-1$ 表示为 $2^kt$ ,先求出 $x=a^t$ ,如果 $x=1$ 那么验证成功,否则检查 $x^2\ mod\ n$ 是不是 $1$ ,如果是 $1$ 那么检查 $x$ 是不是 $n-1$ ,如果不是就验证失败,否则验证成功,以此类推做 $k$ 次。
inline bool MR(LL n){
for (int i=0;i<8;i++) if (!(n%prime[i])) return n==prime[i]; //可以先判掉几个素数
for (int t=1;t<=10;t++){
int k=0;LL x,s;for (x=n-1;!(x&1);x>>=1,k++);x=Pow(rand()%(n-2)+2,x,n);
if (x==1) continue;
for (;k;k--,x=s) {s=Mul(x,x,n);if (s==1) {if (x<n-1) return false;break;}}
if (s>1) return false;
}return true;
}
泼辣的肉Pollard-Rho(PR)可以期望 $O(n^{1\over 4})$ 找出一个 $n$ 的因子 $d$ (感觉好像贼快啊),为了判断 $d$ 是不是素数需要利用MR。大概是这样的:如果 $(x.n)>1$ 那么 $(x,n)$ 就是 $n$ 的一个因子。
怎么找 $x$ ?随机大法好!随机出 $a$ 和 $r$ ,每次 $a'=(a^2+r)\ mod\ n$ (随机数生成器,其实可以随便搞),如果 $(|a-a'|,n)>1$ 说明找到了。但是 $a$ 可能会出现循环,所以需要神奇的Floyd判环。
干嘛这么做,复杂度又是什么?令生成的随机数列为 $\{a_i\}$ ,另一个数列 $\{b_i=a_i\ mod\ d\}$ ( $d$ 是找到的因子),如果 $b_i=b_j\Leftrightarrow d|(a_j-a_i)$ 就说明找到了一组解。跟据生日悖论,$a$ 期望 $\sqrt n$ 出现循环,而 $b$ 期望 $\sqrt d$ 出现循环,所以 $b$ 更容易出现循环,只要在 $a$ 出现循环之前 $b$ 出现循环就意味着找到了一个因子。当然没找到就多做几次啊2333。
inline LL FindD(LL n){
LL x=rand()%(n-1)+1,y=x,r=rand()%(n-1)+1;
for (int i=1,k=1;;i++){
AMOD(x=Mul(x,x,n),r,n-1);x++;if (x==y) return -1;LL GCD=gcd(Abs(x-y),n);
if (GCD>1) return GCD;if (i==k) k<<=1,y=x;
}
}
void PR(LL n){
if (n==1) return;if (MR(n)) {p[++P]=n;return;} //特判
LL D;for (D=FindD(n);D<0;D=FindD(n));PR(D);PR(n/D);
}
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=150000,maxp=10000,prime[]={2,3,5,7,11,13,17,19};
int n,a[maxn+5],b[maxn+5];LL LCM[maxn+5];int P;LL p[maxp+5];
inline LL Mul(LL x,LL y,LL MOD) {return ((x*y-(LL)((DB)x/MOD*y)*MOD)%MOD+MOD)%MOD;}
inline LL Pow(LL w,LL b,LL MOD) {LL s=1;for (;b;b>>=1,w=Mul(w,w,MOD)) if (b&1) s=Mul(s,w,MOD);return s;}
inline bool MR(LL n){
for (int i=0;i<8;i++) if (!(n%prime[i])) return n==prime[i];
for (int t=1;t<=10;t++){
int k=0;LL x,s;for (x=n-1;!(x&1);x>>=1,k++);x=Pow(rand()%(n-2)+2,x,n);
if (x==1) continue;
for (;k;k--,x=s) {s=Mul(x,x,n);if (s==1) {if (x<n-1) return false;break;}}
if (s>1) return false;
}return true;
}
#define Abs(x) ((x)<0?-(x):(x))
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
inline LL lcm(LL a,LL b) {return a/gcd(a,b)*b;}
inline void AMOD(LL &x,LL tem,LL MOD) {if ((x+=tem)>=MOD) x-=MOD;}
inline LL FindD(LL n){
LL x=rand()%(n-1)+1,y=x,r=rand()%(n-1)+1;
for (int i=1,k=1;;i++){
AMOD(x=Mul(x,x,n),r,n-1);x++;if (x==y) return -1;LL GCD=gcd(Abs(x-y),n);
if (GCD>1) return GCD;if (i==k) k<<=1,y=x;
}
}
void PR(LL n){
if (n==1) return;if (MR(n)) {p[++P]=n;return;}
LL D;for (D=FindD(n);D<0;D=FindD(n));PR(D);PR(n/D);
}
int main(){
freopen("program.in","r",stdin);freopen("program.out","w",stdout);
scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),LCM[i]=lcm(a[i],b[i]);
LL GCD=LCM[1];for (int i=2;i<=n;i++) GCD=gcd(GCD,LCM[i]);if (GCD==1) return puts("-1"),0;
PR(GCD);return printf("%lld\n",p[1]),0;
}