题目描述
原题来自：POJ 2891
给定
2n
2n 个正整数
a_1,a_2,\cdots ,a_n
a1
,a2
,⋯,an
和
m_1,m_2,\cdots ,m_n
m1
,m2
,⋯,mn
，求一个最小的正整数
x
x，满足
\forall i\in[1,n],x\equiv a_i\ (\bmod m_i\ )
∀i∈[1,n],x≡ai
(modmi
)，或者给出无解。
输入
多组数据。
每组数据第一行一个整数
n
n；
接下来
n
n 行，每行两个整数
m_i,a_i
mi
,ai
。
输出
对于每组数据，若无解，输出
-1
−1；否则输出一个非负整数，若有多解，输出最小的满足条件的答案。
样例输入
2
8 7
11 9
样例输出
31
提示
数据范围与提示
对于全部数据，所有的输入都是非负的，并且可以用
64
64 位有符号整数表示。保证
1\le n\le 10^5,m_i\gt a_i
1≤n≤105,mi
>ai
。
来源/分类
ybttg 扩展欧几里德算法 中国剩余定理